一、题目描述

给定一个单链表 L：L0→L1→…→Ln-1→Ln ，将其重新排列后变为：L0→Ln→L1→Ln-1→L2→Ln-2→…

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例1:

“

给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.

”

示例2：

“

给定链表 1->2->3->4, 重新排列为 1->4->2->3.

”

二、题目解析

这题属于是链表题的大杂烩了，包含了链表题型中会涉及到的很多思想，非常考研基本功，也难怪字节会考察，同时还希望你能给出最优解。

这道题目很考察基本功和观察能力，最终的结果就是将原链表的前半部分和原链表的后半部分反转之后的链表进行合并得到的。

所以，需要执行以下三个操作。

• 1、寻找出原链表的中点，把链表划分为两个区域
• 2、将右边的链表进行反转
• 3、把这两个区域进行交错合并

1、使用快慢指针寻找链表中点

在链表的头节点设置两个指针 slow、fast，同时将它们向后移动。

每一次，slow 向后移动一步，fast 向后移动两步。

于是，找到了中间节点 5，把链表划分为两个区域。

2、将右边的链表进行反转

3、把这两个区域进行交错合并

属于归并排序的降维版本，这个操作不了解的话可以复习一下归并排序。

三、参考代码

// LeetCode 100 题精讲：https://mp.weixin.qq.com/s/yznC53g46phq3qF7V4-obA
// 作者：程序员吴师兄
// 重排链表（LeetCode 143）：https://leetcode.cn/problems/reorder-list/
class Solution {
    public void reorderList(ListNode head) {
    // a、寻找出原链表的中点，把链表划分为两个区域
        // b、将右边的链表进行反转
        // c、把这两个区域进行交错合并
      
        // 1、使用快慢指针寻找出链表的中点来 
       // *******************************************************
        // 对于 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8
        // 中间节点值为 5
        // 所以左边区域为 1 -> 2 -> 3 -> 4 -> 5
        // 右边区域为 6 -> 7 -> 8
        // 但在视频讲解中，我把 5 归为了右边区域，这是一个错误
        // 虽然这个错误并不影响结果，因为合并过程都是一样的逻辑
        // *******************************************************
        ListNode mid = middleNode(head);

        // 2、基于 mid 这个中点，将链表划分为两个区域

        // 左边的区域开头节点是 head
        ListNode leftHead = head;

        // 右边的区域开头节点是 mid.next
        ListNode rightHead = mid.next;

        // 将链表断开，就形成了两个链表了
        mid.next = null;

        // 3、将右边的链表进行反转
        rightHead = reverseList(rightHead);

        // 4、将这两个链表进行合并操作，即进行【交错拼接】
        while( leftHead != null && rightHead != null){

            // 拼接过程如下
            // 5、先记录左区域、右区域【接下来将有访问的两个节点】
            ListNode leftHeadNext = leftHead.next;

            ListNode rightHeadNext = rightHead.next;

            // 6、左边连接右边的开头
            leftHead.next = rightHead;

            // 7、leftHead 已经处理好，移动到下一个节点，即刚刚记录好的节点
            leftHead = leftHeadNext;

            // 8、右边连接左边的开头
            rightHead.next = leftHead;

            // 9、rightHead 已经处理好，移动到下一个节点，即刚刚记录好的节点
            rightHead = rightHeadNext;
            
        }

    }

    // LeetCode 876 : 链表的中间节点
    public ListNode middleNode(ListNode head) {

        ListNode fast = head;

        ListNode slow = head;

        while(fast != null && fast.next != null){

            fast = fast.next.next;

            slow = slow.next;
        }

        return slow;

    }

    // LeetCode 206 : 反转链表
    public ListNode reverseList(ListNode head) {

        // 寻找递归终止条件
        // 1、head 指向的结点为 null 
        // 2、head 指向的结点的下一个结点为 null 
        // 在这两种情况下，反转之后的结果还是它自己本身
        if( head == null || head.next == null)  return head;

        // 不断的通过递归调用，直到无法递归下去，递归的最小粒度是在最后一个节点
        // 因为到最后一个节点的时候，由于当前节点 head 的 next 节点是空，所以会直接返回 head
        ListNode cur = reverseList(head.next);

        // 比如原链表为 1 --> 2 --> 3 --> 4 --> 5
        // 第一次执行下面代码的时候，head 为 4，那么 head.next = 5
        // 那么 head.next.next 就是 5.next ，意思就是去设置 5 的下一个节点
        // 等号右侧为 head，意思就是设置 5 的下一个节点是 4

        // 这里出现了两个 next
        // 第一个 next 是「获取」 head 的下一节点
        // 第二个 next 是「设置」 当前节点的下一节点为等号右侧的值
        head.next.next = head;


        // head 原来的下一节点指向自己，所以 head 自己本身就不能再指向原来的下一节点了
        // 否则会发生无限循环
        head.next = null;

        // 我们把每次反转后的结果传递给上一层
        return cur;
    }
}

玩转 LeetCode 高频 100 题系列正在更新，全系列题目和所有视频讲解可点击下方图片查看：

数组篇

1、LeetCode 283：移动零

2、LeetCode 75：颜色分类

3、LeetCode 26：删除有序数组中的重复项

4、LeetCode 88：合并两个有序数组

链表篇

1、LeetCode 876、链表的中间结点

2、字节实习一面，不画图，真的想不清楚！

系列介绍：LeetCode 刷多少题能进大厂面试?

一、题目描述

给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。示例 1：

输入：head = [4,2,1,3]
输出：[1,2,3,4]

示例 2：

输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]

示例 3：

输入：head = []
输出：[] 

提示：

• 链表中节点的数目在范围 [0, 5 * 10^4] 内
• -10^5 <= Node.val <= 10^5

进阶：你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？

二、题目解析

我在这道题目的评论区看到有两个同学提到字节考察过，并且都是要实现 O(1) 的空间复杂度才过关。

“

这道题目确实挺有难度的，不画图，真的想不清楚。

”

题目要求时间空间复杂度分别为 O(nlogn) 和 O(1) ，根据时间复杂度和题目中的排序两个字，可以联想到归并排序和快速排序。

所以，本题有两种解法：归并排序和快速排序。

这里我们先用归并排序的思路进行处理，其中合并的基本操作如下：

• 1、长度为 1 的链表和长度为 1 的链表合并后，形成一个长度为 2 的链表
• 2、长度为 2 的链表和长度为 2 的链表合并后，形成一个长度为 4 的链表
• 。。。

而由于合并过程中操作的是链表，所以需要有断链和重新连接的过程。

具体操作步骤如下：

1、先获取链表长度，基于这个长度才能知道后续合并到什么时候截止

2、设置三个指针 prev、 curr、 next。

其中， prev表示已经排序好的链表的【尾节点】。

curr 一开始设置为准备排序的那些节点的【首节点】，然后向后移动，获取相应的节点，到达所有正在准备排序的那些节点的【尾节点】位置。

next 表示接下来需要排序的那些节点的【首节点】。

3、断开 prev 与 curr 的连接，再断开 curr 与 next 的连接。

4、把 curr 访问的这些节点划分为两个区域，区域的长度取决于此时进行到了长度为多少的链表进行合并操作，一个是左链表，一个是右链表，把这两个链表进行合并操作。

5、合并成功之后，prev 移动到尾部，curr 来到 next 的位置，继续后面的归并操作。

6、这样一轮下来，已经把长度为 2 的链表和长度为 2 的链表合并，形成了一个长度为 4 的链表。

7、接下来，只需要执行上述同样的操作，唯一的修改点在于合并的子链表长度变成了 4。

三、参考代码

// LeetCode 100 题精讲：https://mp.weixin.qq.com/s/yznC53g46phq3qF7V4-obA
// 作者：程序员吴师兄
// 排序链表（LeetCode 148）：https://leetcode.cn/problems/sort-list/
class Solution {
    public ListNode sortList(ListNode head) {

        // 获链表的总长度
        int length = 0;

        // 从链表的头节点开始访问
        ListNode node = head;

        // 利用 while 循环，可以统计出链表的节点个数，即长度
        while (node != null) {

            length++;

            node = node.next;

        }

        // 在原链表的头部设置一个虚拟头节点
        // 因为可能会操作到原链表的头节点
        // 设置了虚拟头节点后，原链表的头节点和原链表的其它节点地位一样
        ListNode dummyHead = new ListNode(0, head);

        // 利用 for 循环，执行合并的操作
        // 长度为 1 的链表和长度为 1 的链表合并后，形成一个长度为 2 的链表
        // 长度为 2 的链表和长度为 2 的链表合并后，形成一个长度为 4 的链表
        // 长度为 4 的链表和长度为 4 的链表合并后，形成一个长度为 8 的链表
        // 长度为 8 的链表和长度为 8 的链表合并后，形成一个长度为 16 的链表
        // 也有可能是，长度为 8 的链表和长度为 5 的链表合并后，形成一个长度为 13 的链表
        // 但是，每次合并过程中，子链表都会想要扩充为原来的两倍
        // 直到子链表想要扩充的长度超过了 length
        for (int subLength = 1; subLength < length; subLength *= 2) {

            // 整个归并过程分为三个步骤
            // 1、不停的划分，直到无法划分为止
            // 2、开始两两合并
            // 3、每次合并之后的结果都需要连接起来

            // 每次都把结果连接到 dummyHead，因此先记录一下
            // prev 表示已经排序好的链表的【尾节点】
            ListNode prev = dummyHead;
            
            // dummyHead 的后面节点才是原链表的节点，需要把它们进行划分
            // curr 表示所有正在准备排序的那些节点的【尾节点】
            ListNode curr = dummyHead.next;

            // 利用 while 循环，寻找出每次划分后子链表的头节点
            while (curr != null) {
                
                // 每次都是两个子链表开始合并

                // 1、先寻找出【左子链表】，长度为 subLength
                ListNode head1 = curr;

                // 通过 for 循环，找出 subLength 个节点来
                // curr 的索引为 0 ，需要再找 subLength - 1 个节点来
                for (int i = 1; i < subLength && curr.next != null; i++) {

                    curr = curr.next;

                }

                // 2、再寻找出【右子链表】，长度最多为 subLength，甚至有可能长度为 0
                ListNode head2 = curr.next;

                // 此时，需要将【左子链表】与【右子链表】的连接断开
                curr.next = null;

                // curr 来到【右子链表】的头部
                curr = head2;

                // 通过 for 循环，找出【右子链表】的那些节点来
                // 【右子链表】的节点个数可能达不到 subLength，甚至只有 1 个或者 0 个节点
                for (int i = 1; i < subLength && curr != null && curr.next != null; i++) {

                    curr = curr.next;

                }

                // 获取到【右子链表】之后，需要把它和后续链表断开
                // next 表示接下来需要排序的那些节点的【首节点】
                ListNode next = null;

                // 如果 curr != null，那么说明【右子链表】的节点个数达到了 subLength 个，并且后续还有节点
                if (curr != null) {
                    
                    // 记录一下后面节点
                    next = curr.next;

                    // 再将【右子链表】和后续链表断开
                    curr.next = null;

                }

                // 将【左子链表】与【右子链表】合并
                ListNode merged = mergeTwoLists(head1, head2);

                // 合并之后的结果需要连接到前一个链表
                prev.next = merged;

                // prev 来到链表的尾部，是下一个即将合成链表之后的前一个链表的尾节点
                while (prev.next != null) {

                    prev = prev.next;

                }

                // curr 来到 next，处理后面的节点
                curr = next;
            }

        }

        return dummyHead.next;
    }

    // 合并两个有序链表的代码
    private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        // 一开始设置一个虚拟节点，它的值为 -1，它的值可以设置为任何的数，因为我们根本不需要使用它的值
        ListNode dummy = new ListNode(-1);

        // 设置一个指针，指向虚拟节点
        ListNode pre = dummy;

        // 通过一个循环，不断的比较 l1 和 l2 中当前节点值的大小，直到 l1 或者 l2 遍历完毕为止
        while (l1 != null && l2 != null) {
            // 如果 l1 当前节点的值小于等于了 l2 当前节点的值
            if (l1.val <= l2.val) {
                // 让 pre 指向节点的 next 指针指向这个更小值的节点
                // 即指向 l1
                pre.next = l1;
                // 让 l1 向后移动
                l1 = l1.next;
            }else {
                // 让 pre 指向节点的 next 指针指向这个更小值的节点
                // 即指向 l2
                pre.next =l2;
                // 让 l2 向后移动
                l2 = l2.next;
            }
            // 让 pre 向后移动
            pre = pre.next;
        }

        // 跳出循环后，l1 或者 l2 中可能有剩余的节点没有被观察过
        // 直接把剩下的节点加入到 pre 的 next 指针位置

        // 如果 l1 中还有节点
        if (l1 != null) {
            // 把 l1 中剩下的节点全部加入到 pre 的 next 指针位置
            pre.next = l1;
        }

        // 如果 l2 中还有节点
        if (l2 != null) {
            // 把 l2 中剩下的节点全部加入到 pre 的 next 指针位置
            pre.next = l2;
        }

        // 最后返回虚拟节点的 next 指针
        return dummy.next;
    }
}

玩转 LeetCode 高频 100 题系列正在更新，全系列题目和所有视频讲解可点击下方图片查看：

数组篇

1、LeetCode 283：移动零

2、LeetCode 75：颜色分类

3、LeetCode 26：删除有序数组中的重复项

4、LeetCode 88：合并两个有序数组

链表篇

1、LeetCode 876、链表的中间结点

系列介绍：LeetCode 刷多少题能进大厂面试?

一、题目描述

给定一个头结点为 head 的非空单链表，返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

示例 1：

输入：[1,2,3,4,5]
输出：此列表中的结点 3 (序列化形式：[3,4,5])
返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。
注意，我们返回了一个 ListNode 类型的对象 ans，这样：
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.

示例 2：

输入：[1,2,3,4,5,6]
输出：此列表中的结点 4 (序列化形式：[4,5,6])
由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。

提示：

• 给定链表的结点数介于 1 和 100 之间。

二、题目解析

我个人认为这道题目是最好理解快慢指针这个知识点了。

废话不多说，直接先来看动画演示！

根据这个动画，不难理解整体的思路如下：

1、设置两个指针，一开始都指向链表的头节点；

2、接下来，让这两个指针向前移动；

3、如果可以移动，那么就会让快指针每次移动两步，慢指针每次移动一步；

4、而快指针可以移动两步的前提就是当前节点不为空，同时下一节点也不为空，这样才能保证 fast.next 有值、fast.next.next 有值

5、最后，slow 指向的就是中间节点。

三、参考代码

// LeetCode 100 题精讲：https://mp.weixin.qq.com/s/yznC53g46phq3qF7V4-obA
// 作者：程序员吴师兄
// 链表的中间结点（LeetCode 876）：https://leetcode.cn/problems/middle-of-the-linked-list/
class Solution {
    public ListNode middleNode(ListNode head) {

        // 设置两个指针，一开始都指向链表的头节点
        ListNode slow = head;

        ListNode fast = head;

        // 接下来，让这两个指针向前移动
        // 如果可以移动，那么就会让快指针每次移动两步，慢指针每次移动一步
        // 而快指针可以移动两步的前提就是当前节点不为空，同时下一节点也不为空
        // 这样才能保证 fast.next 有值、fast.next.next 有值
        while(fast != null && fast.next != null){

            // 慢指针每次移动一步
            slow = slow.next;

            // 快指针每次移动两步
            fast = fast.next.next;
        }

        // 最后，slow 指向的就是中间节点
        return slow;

    }
}

玩转 LeetCode 高频 100 题系列正在更新：

数组篇

1、LeetCode 283：移动零

2、LeetCode 75：颜色分类

3、LeetCode 26：删除有序数组中的重复项

4、LeetCode 88：合并两个有序数组

系列介绍：LeetCode 刷多少题能进大厂面试?

一、题目描述

给你一个 升序排列 的数组 nums ，请你原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。

由于在某些语言中不能改变数组的长度，所以必须将结果放在数组nums的第一部分。更规范地说，如果在删除重复项之后有 k 个元素，那么 nums 的前 k 个元素应该保存最终结果。

将最终结果插入 nums 的前 k 个位置后返回 k 。

不要使用额外的空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

二、题目解析

这属于一道简单题，但还是有一些同学卡住了。

每个人都是从这种状态过来的，加油，会越来越快。

整个操作的过程可以理解为是一个筛选的过程，即只有符合要求的元素才有资格留下来。

由于数组是一个升序排列，因此重复的元素一定是相邻的，这些重复的元素只能保留一个，重复元素中剩余元素没有资格留下来，它们的位置会被后续有资格保留下来的元素覆盖掉。

三、参考代码

// LeetCode 100 题精讲：https://mp.weixin.qq.com/s/yznC53g46phq3qF7V4-obA
// 作者：程序员吴师兄
// 删除有序数组中的重复项（LeetCode 26）:https://leetcode.cn/problems/remove-duplicates-from-sorted-array/submissions/
class Solution {
    public int removeDuplicates(int[] nums) {

        // 指针 i 进行数组遍历
        int n = nums.length;

        // 指针 j 指向即将被赋值的位置
        int j = 0;

        // 开始对数组进行遍历
        for (int i = 0 ; i < n ; i++) {

            // 进行筛选
            if ( i == 0 ||  nums[i] != nums[i - 1]) {
                // 赋值
                nums[j] = nums[i];

                // j 移动
                j++;
            }
        }

        // 获取结果
        return j ;
    }
}

玩转 LeetCode 高频 100 题系列正在更新：

数组篇

1、LeetCode 283：移动零

2、LeetCode 75：颜色分类

系列介绍：LeetCode 刷多少题能进大厂面试?

玩转 LeetCode 高频 100 题系列正在更新：

数组篇

1、LeetCode 283：移动零

系列介绍：LeetCode 刷多少题能进大厂面试?