Appearance
05链表：如何利用“假头、新链表、双指针”解决链表题？（下）
在上一讲中，我给你介绍了解决链表问题的"三板斧"中的第一斧：假头，你知道了带假头的链表一共有 6 种基本的操作，分别是初始化、追加结点、头部插入结点、查找结点、插入指定位置之前和删除结点。
如果说三板斧的第一斧平平淡淡，大巧不工；第二斧就是鬼斧神工，生成新链表 后，链表的交换、反转求解都会变得极其简单 ；第三斧则是奇思妙想，双指针 （也叫快慢指针）用在链表上经常可以解决一些单个指针难以解决的问题。学会了这两种思路，算法面试中的链表题就如同探囊取物了。
注：大部分链表题主要考查动手能力，因此在本讲将不再按照"分析四步法"进行讲解。
三板斧的第二斧：新链表
做链表的反转、交换等操作时，我不建议直接在原来的链表上进行操作 。一种可取的思路是，把这些操作想象成要生成新的链表，然后借助这些新的链表，完成原本比较复杂的操作。这个方法就是我们今天要讲的**"第二斧"------新链表**。
接下来，我将采用这种新思路，带你解决一些面试中经常会遇到的疑难题目。
例 1：链表反转
【题目】输入一个链表的头结点，反转该链表，并返回反转后链表的头结点。
输入：1->2->3
输出：3->2->1
【分析 】这里借助假头和新链表求解，思路如下：
建立一个新的带假头的空链表；
遍历旧链表，依次取出旧链表中的每个结点；
采用头部插入的方法放到新链表中；
返回 dummy.next。
【画图】这里我们利用示意图演示如下：
【代码】对应的代码如下（解析在注释里）：
java
class Solution {
public ListNode reverseList(ListNode head) {
// 建立一个新的带假头的新链表
ListNode dummy = new ListNode();
// 开始遍历旧链表
while (head != null) {
ListNode tmp = head.next;
// 把旧链表中的结点取出来，采用头部插入的方法添加到新链表中
head.next = dummy.next;
dummy.next = head;
head = tmp;
}
// 返回新链表的头，注意，不要返回dummy!!
return dummy.next;
}
}复杂度分析：每个结点只遍历一次，所以时间复杂度为 O(N)，内存空间只使用了常量空间，因此空间复杂度为 O(1)。
【小结 】仔细查看代码之后，链表反转的考点 就是之前我们学到的基本操作：假头，头部插入法，再结合今天学习的新链表的思路。可以总结如下：
例 2：删除结点
【题目】给定一个链表头及一个整数值，要求把链表里面等于整数值的结点都从链表中移除出去。
输入：1->2->3->2->4, remove = 2
输出：1->3->4。
解释：要移除的整数值是 2。那么移除之后，返回的结果应该是 1->3->4。
【分析】这里我们不采用在原来的链表上进行删除的办法，而是采用新链表的操作思路：
建立一个新的带假头的空链表；
遍历旧链表，依次取出旧链表中的每个点，如果不删除这个结点，那么就采用尾部插入方法接到新链表中。
可以发现，在这里没有出现结点交换的操作。采用新链表的思路，避免了在原链表上不停地做结点的删除。为了方便你理解，我制作了动图演示，如下所示：
【代码】基于以上思想，可以写出代码如下（解析在注释里）：
java
class Solution {
public ListNode removeElements(ListNode head, int val) {
// 生成一个新链表
ListNode dummy = new ListNode();
ListNode tail = dummy;
// 依次取出旧链表中的每个结点
ListNode p = head;
while (p != null) {
ListNode back = p.next;
// 如果结点值需要保留，那么采用属部追加的方法
// 添加到新链表中
if (p.val != val) {
tail.next = p;
tail = p;
}
p = back;
}
// 注意设置尾巴的next为空
tail.next = null;
// 注意返回的是dummy.next
return dummy.next;
}
}复杂度分析：时间复杂度 O(N)，空间复杂度 O(1)。
【小结 】我们将这道题的考点层层剥离之后，就只剩下生成 dummy 新链表，尾巴追加新结点，以及新链表的思路。关于解决这道这类题目的思路、重点以及分析方法，建议你先尝试自己梳理总结，再来看我给出的思维导图：
如果我们仔细对比链表反转与删除结点，会发现，这两者的不同之处在于：
链表反转使用的是头部插入的方法
删除结点采用的是尾部追加的方法
只是换了一个考点，题目就完全大变样了。如果我们再严格地对比这两个题目，可以发现：
链表反转时，头部插入是无条件的
删除结点时，尾部 append 是有条件的
这种条件的千变万化，会带来很多有趣的题目。比如下面这道练习题。
练习题 1：给定一个排序链表，删除重复出现的元素，使得每个元素只出现一次。
输入: 1->1->2->3->3
输出: 1->2->3
练习题 2：给定一个排序链表，删除重复出现的元素，只留下没有重复出现的元素。
输入：1->1->2->3->3
输出：2
你可以把答案或者思考的过程写在评论区，我们一起讨论。
例 3 ：合并
【题目】合并给定的两个有序链表。
输入：a = 1->4->6, b = 3->5->7
输出：1->3->4->5->6->7
【分析 】首先应该是生成一个带假头的新链表 C，然后把 A，B 中的元素从小到大，依次添加到新生成的链表 C 中。因此，我们还需要使用到尾部插入法。
具体操作方法如下。
第一步：A，B 两个指针分别指向 A，B 链表的表头。
第二步：依次取出 A，B 两个指针中更小的值加入新链表中。
第三步：返回 C 链表假头的 next。
具体演示如下所示：
【代码】有了前面的思路，可以写出代码如下（解析在注释里）：
java
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
// 首先生成空链表
ListNode dummy = new ListNode();
ListNode tail = dummy;
// 遍历两个有序链表,每次只取一个结点append到新链表里面
while (l1 != null || l2 != null) {
// 如果l2链表为空，或者l1链表里面的值更小，那么取l1结点追加到
// 新链表尾部
if (l2 == null || l1 != null && l1.val < l2.val) {
tail.next = l1;
tail = l1;
l1 = l1.next;
} else {
// 其他情况，则把l2结点添加到新链表尾部
tail.next = l2;
tail = l2;
l2 = l2.next;
}
}
// 注意：这里一定要记得把tail.next设置为空。
// 虽然这个题可能并不需要，但是应该养成收尾的好习惯
tail.next = null;
// 返回dummy.next, 不要返回dummy!!
return dummy.next;
}
}复杂度分析：时间复杂度 O(N)，空间复杂度 O(1)。
【小结】如果我们再分析一下这道题目，可以发现考点仍然是：
生成 dummy 新链表
选择结点往新链表尾部追加数据
此时的尾部 append 是有 条件的：需要从两个链表头中选择一个较小的数据进行追加。当然，有条件的 append 还可以变成各种其他的条件来操作。不过即使千变万化，只要你看清楚题的考点，就能轻松应对、。
那么这里我们不妨再选择其中一个考点"选择较小的数"进行练习。在原题中，只有两个链表，所以可以直接通过比较得到较小的结点。可是如果有 k 个链表要合并的时候，又应该怎么做呢？比如下面这道练习题：
练习题 3：给定 k 个有序链表，合并成一个有序链表
输入：[1->4->5，1->3->4, 2->6]
输出：[1->1->2->3->4->4->5->6]
你可以把答案或者思考的过程写在评论区，我们一起讨论。
例 4：交换链表中的结点
【题目】给定一个链表，需要将里面的结点两两交换。
输入：[1->2->3->4->5->6]
输出：[2->1->4->3->6->5]
【分析】经过观察发现，只不过把偶数位置与奇数位置的结点进行了交换。为了避免在原始链表中进行结点间的交换操作，我们可以采用如下方法：
生成两个新链表，一个用来存放奇数位置结点的链表 odd，一个用来存放偶数位置结点的链表 even；
遍历旧链表，并且把奇数位置上的结点放到 odd 链表中，把偶数位置的结点放到链表 even 中；
合并 odd 链表与 even 链表。
为了方便你理解，我同样制作了动图演示，如下：
到这里，新增链表已经从一条变成了两条，来帮助我们解决这道题目。
【代码】有了思路，我们可以写出代码如下（解析在注释里）：
java
class Solution {
private ListNode mergeList(ListNode a, ListNode b) {
ListNode dummy = new ListNode();
ListNode tail = dummy;
// 合并两个链表
while (a != null || b != null) {
// 如果a不空，那么先取a结点
if (a != null) {
tail.next = a;
tail = a;
a = a.next;
}
// 如果b不空，再取b结点
if (b != null) {
tail.next = b;
tail = b;
b = b.next;
}
}
// 注意收尾
tail.next = null;
return dummy.next;
}
public ListNode swapPairs(ListNode head) {
// 生成奇数index应该存放的链表
ListNode oddDummy = new ListNode();
ListNode oddTail = oddDummy;
// 生成偶数index应该存放的链表
ListNode evenDummy = new ListNode();
ListNode evenTail = evenDummy;
int index = 0;
ListNode p = head;
while (p != null) {
ListNode back = p.next;
// 如果是偶数，放到偶数链表中
if ((index & 0x01) == 0) {
evenTail.next = p;
evenTail = p;
} else {
// 如果是奇数，放到奇数链表中
oddTail.next = p;
oddTail = p;
}
index++;
p = back;
}
// 注意两个链表的收尾
oddTail.next = null;
evenTail.next = null;
// 注意这里传入的是oddDummy.next和evenDummy.next
return mergeList(oddDummy.next, evenDummy.next);
}
}复杂度分析：每个结点会访问两次，拆分一次，合并一次，所以时间复杂度为 O(N)，空间复杂度为 O(1)。
【小结】这道题的考点也比较明确了，可以拆分出以下考点：
拆分链表
新链表的思路
合并链表的操作
尤其需要注意的是，使用新链表思路时，可以通过生成多条新链表来解决以前处理起来比较麻烦的问题。至此，我们一起进一步扩展了链表知识。此外，还发现了一些小型的组合操作，比如：**拆分链表，合并链表。**在合并时，如果按照不同的条件合并，就需要写出不一样的合并代码，结合前面例 3，可以知道合并分两种：
有序合并
先后合并
到这里可以总结出我们更加丰富的知识路线图，如下图所示：
在这道题中，链表是两两成对进行了反转 ，那么如果是 k 个一组进行反转应该怎么办呢？我们再来看看与交换有关的练习题。
练习题 4：给定一个链表，要求将链表 k 个一组进行反转，如果最后一组不足 k 个，那么不反转。返回反转之后的链表。
输入：A = [1, 2, 3, 4, 5], k = 2
输出: [2, 1, 4, 3, 5]
练习题 5：给定一个链表，从链表尾部开始，k 个一组进行反转，如果左边的分组不足 k 个，那么不反转。返回反转之后的链表。
输入：A = [1, 2, 3, 4, 5], k = 2
输出：[1, 3, 2, 5, 4]
解释：注意是从链表的尾部开始k个一组的。所以这里是[1], [2, 3], [4, 5]这样分组来进行反转。
三板斧的第三斧：双指针
虽然新链表的思路非常有趣，但是关于它的更多探索还是应该留给你自己。收拾好行囊，我们将要去看更加瑰丽的奇景------双指针。
双指针，顾名思义就是两个指针在链表上移动。实际上，我们在前面链表的查找中已经使用过双指针了：比如链表中指定位置插入一个新结点，就使用了两个指针，一前一后两个指针在链表上前进。
其实两个指针在链表上前进时，有很多种形式，常见的主要有以下两种。
间隔指针：前面的指针先走一步，然后后面的指针再一起走；前面的指针先走 k 步，后面的指针再一起走。
快慢指针：两个指针的速度一快一慢前进，比如一个每次走一步，一个每次走两步。
接下来，我们来看看双指针能解决什么类型的问题。
例 5：链表的倒数第 k 个结点
【题目 】给定一个链表，删除链表中的倒数第 k 个结点。这里我们认为最后一个结点是倒数第 1 个。
输入：1->2->3, k = 2
输出： 1->3
【分析】首先第一种常规思路是，先统计出整个链表的长度 len, 再去取第 len-k 结点的前驱进行删除。
但是，面试的时候，面试官往往会加一个限制条件 ：只能遍历链表一次。
以后凡是遇到链表题，看到这句话，实际上就是在告诉你"用双指针吧"。思路如下：
在原链表前面加上 dummy，变成带假头的链表
front 指针从 dummy 开始，走 k 步，然后停下来
back 指针指向链表 dummy 假头
然后两个指针再一起走
当 front 指针指向最后一个结点 时，back 指针刚好指向倒数第 k 个结点的前驱。
解题思路有了，还有两个细节需要你特别注意。
【细节 1】你需要小心处理三种情况：
链表长度 < k，此时什么也不做；
链表长度 == k，此时删除原来的链表头结点；
链表长度 > k，此时找到倒数第 k 个结点 的前驱，然后删除倒数第 k 个结点。
接下来，我们分别讨论这三种情况。
情况 1：链表长度小于 k。front 指针会先走 k 步，如果链表长度小于 k，那么必然会导致 front 指针行走的步数小于 k，此时应该什么也不做。
情况 2：链表长度等于 k。此时需要删除倒数第 k 个结点，也就是旧链表的 head 结点。
当 front 指针先走完 k 步之后，back 指针刚好位于 dummy 结点。而 dummy 结点就是倒数第 k+1 个结点，那么此时可以直接通过 back 指针删除它后面的结点（刚好是 head，也就是倒数第 k 个）。
情况 3：链表长度大于 k。back 指针刚好位于倒数第 k+1 个结点，此时可以直接通过 back 指针删除它后面的结点（刚好是倒数第 k 个)。
我们发现：情况 2 和情况 3 实际上都是用 back 指针来删除后面的结点。因此，这两种情况可以一起处理。
【细节 2 】任何时候，front 最后停下来的位置一定 要位于链表的最后一个结点。这是因为：要想删除倒数第 k 个结点的前驱结点，需要 back 刚好指向倒数第 k+1 个结点，那么就必须要让 front 非空，即指向倒数第一个结点。
【代码】有了思路以及相应的细节，我们就可以利用代码来解决问题了（解析在注释里）：
java
class Solution {
public ListNode removeNthFromEnd(ListNode head, int k) {
// 将链表改造成带假头的链表
ListNode dummy = new ListNode();
dummy.next = head;
// 链表长度
int preWalkedSteps = 0;
// front指针从dummy开始先走k步
ListNode front = dummy;
// 注意front不能为空，需要指向链表的最后一个结点
while (preWalkedSteps < k &&
front != null && front.next != null) {
front = front.next;
preWalkedSteps++;
}
// back指针指向dummy，然后front与back指针一起走
ListNode back = dummy;
// 注意front不能为空，需要指向链表的最后一个结点
while (front != null && front.next != null) {
back = back.next;
front = front.next;
}
// 如果preWalkedSteps == k
// 说明处于情况2和情况3，需要删除倒数第k个结点
if (preWalkedSteps == k) {
back.next = back.next.next;
}
// 返回新的链表头
return dummy.next;
}
}复杂度分析：时间复杂度 O(N)，空间复杂度 O(1)
【小结】当做完这道题之后，我们可以进一步完善双指针的技巧，总结的思维导图如下：
然后，我们再来总结一下这道题目的考点。首先除了思路"双指针"以外，你还需要注意写代码的技巧。
将旧链表改造成带 dummy 结点的链表，方便删除 head 结点。这是能让情况 2 和情况 3 统一处理的关键。
让指针指向链表最后一个结点的 while 语句的写法。
利用移动步数来判断链表长度与 k 的关系。
接下来我们一起看一下双指针的另外一种形式，快慢指针。
例 6：拆分链表
【题目】给定一个链表，需要把链表从中间拆分成长度相等的两半（如果链表长度为奇数，那么拆分之后，前半部分长度更长一点）。
输入：[1->2->3->4->5]
输出：[1->2->3, 4->5]
【分析】我们需要分为 2 步：
找到链表的中间结点
从中间结点把链表分为两半
那么问题是，如何找到中间结点呢？如果是首先求出链表的长度，然后再利用 getPreNode(len/2) 函数的前驱，再把链表拆分成两半。
但是，这可能不是面试官想要的解法，因为这种解法会将链表遍历两遍，面试官可能会说："只能遍历一次"。又听到了这个声音，这就是告诉你需要用双指针了。
所以问题的关键就是如何使用双指针找到链表的中间结点，可以采用如下办法：
假设链表头在左边，尾巴在右边，两个指针 s1、s2 从链表头开始往右走；
s1 表示每次只往前走一步，s2 则表示每次只往前走 2 步；
在同样的时间内，当 s2 指向链表的末尾，s1 指针便指向链表的中间结点。
只是在写代码的时候，需要特别注意以下 2 点：
1.当有偶数 个结点，s2 是空指针 ，此时，s1 位于后半部分指针的头部，因此需要返回s1 的前驱；
2.当有奇数 个结点，s2 是最后一个结点 ，此时 s1 指针位于前半部分的最后，直接返回 s1即可。
如果找到了中间结点，那么就可以直接进行拆分了。
【代码】接下来我们就实现拆分链表的逻辑，代码如下（解析在注释里）：
java
class Solution {
private ListNode findMiddleNode(ListNode head) {
// 注意这里转化为带假头的链表，免去了空链表的判断
ListNode dummy = new ListNode();
dummy.next = head;
// 注意，假头并不算是链表的一部分，所以这里是从head开始走
ListNode s2 = head;
ListNode s1 = head;
// dummy就是head的前驱，所以pre要指向dummy.
ListNode pre = dummy;
// 两个指针开始同时走
// 因为s2指针每次都要走两步，所以判空需要这样判断。
while (s2 != null && s2.next != null) {
pre = s1;
s1 = s1.next;
s2 = s2.next.next;
}
// 当有偶数个结点的时候，s2是空指针，
// 此时，s1位于后半部分指针的头部，因此需要返回s1的前驱。
// 当有奇数个结点的时候，s2是最后一个结点，
// 此时s1指针位于前半部分的最后，直接返回s1即可。
return s2 != null ? s1 : pre;
}
public ListNode[] split(ListNode head) {
// 这里获取了链表的中间结点
ListNode mid = findMiddleNode(head);
// 拿到链表的中间结点之后，可以得到链表的后半部分的开头
ListNode back = mid.next;
// 把链表拆分为两半
mid.next = null;
// 返回两个链表的头部
return new ListNode[]{head, back};
}
}复杂度分析：时间复杂度 O(N)，空间复杂度 O(1)。
【小结 】这道题的核心就是如何通过双指针找到链表的中间结点。考点还是清晰明了，我们可以再将双指针的分析要点总结如下：
不过对于这道题，我想给你留几个有趣的小问题，可以帮助你加深代码的理解，希望你可以尝试回答以下两个问题，并写在留言区，我们一起讨论。
为什么没有判断空链表，对于空链表的支持是怎么完成的？
为什么 s1, s2 要从 head 开始走，如果从 dummy 开始走可以吗？如果可以，会有什么样的代码改动？
练习题 6： 将一个链表进行重排，如果我们用 L[x] 表示链表的第 x 个结点（从 0 开始）。将链表 L[0]->L[1]->L[2]->L[3]-> .... ->L[N-1] 重新排列为 L[0]->L[N-1]->L[1]->L[N-2]->L[2]->L[N-3].....。
输入：1->2->3->4->5
输出：1->5->2->4->3
例 7：链表环问题
【题目】给定一个链表，原本的链表尾巴如果不为空，并且指向了链表的中间结点，这样我们就认为这个链表存在一个环。给定一个链表，判断链表中是否存在环？
【分析】首先，如果链表中存在环，只用一个指针遍历肯定是永无止境的，这一个指针会在环里面打转。因此，我们可以再次利用双指针，s1，s2 两个指针都从链表头开始，s1 指针表示每次只往前走一步，s2 指针则是每次只往前走两步。那么链表最终只有两种情况：
1.s1 == s2，这个时候链表存在环；
2.s1 != s2，这个时候链表不存在环。
不过我们还是需要处理两种边界条件：
当为空链表的时候，s1 == s2，但是实际上此时链表无环；
当链表中只存在一个结点，并且无环的时候，运行的结果也会是 s1 == s2。
这两种边界条件的处理，只需要特殊判断一下即可。
【代码】有了前面了思路，那么我们就可以写出解问题的代码了（解析在注释里）：
java
public class Solution {
public boolean hasCycle(ListNode head) {
// 空链表和只有一个结点的链表的实现。
if (head == null || head.next == null) {
return false;
}
// 分别设置两个快慢指针，他们都从head出发。
// s1表示慢指针，一次只走一步
// s2表示快指针，一次走两步
ListNode s1 = head;
ListNode s2 = head;
// 开始走动两个指针，
// 当相遇到的时候就停下来
while (s2 != null && s2.next != null) {
s2 = s2.next.next;
s1 = s1.next;
if (s1 == s2) {
break;
}
}
// 判断是否有环。如果有环，那么两个指针必定相遇。
return s1 == s2;
}
}复杂度分析：时间复杂度为 O(N)，空间复杂度为 O(1)。
【小结】至此，我们完成了快慢指针的学习，可以在知识图谱中加上链表环问题了，如下图所示：
这里我还想给你留一个小问题：在寻找链表环的过程中，对于两种特殊情况，我们实际上进行了特殊判断，那么有没有什么办法可以避免这种特殊的断呢？
小提示：想想我们之前学习过的假头。
老规矩，希望你尝试思考并把想法写在留言区，期待和你一起讨论。另外，我也会根据大家的留言反馈，不定时输出加餐内容，比如练习题详解、留言区问题点评等。
【扩展】在面试中，伴随着链表环问题的，往往还有后招：如果链表中存在环，能不能把形成环的那个结点找出来？
我们可以把这个问题转化成一个数学问题。我们一起看一下下面这张图：
这里我们只考虑链表存在环的情况。假设 s1 慢指针与 s2 快指针在环中某个位置相遇。此时：
s1 指针走过的路径长度为 a = x + y
s2 指针走过的路径长度为 b = x + y + n * (y + z)
由于两个指针都是从同一个地点出发，s2 指针走得更快，那么走的长度肯定是 s1 指针的两倍。所以可以得到 b = 2a，即 b = x + y + n * (y + z) = 2x + 2y
由此，可以推导出 x = n * (y + z) - y = (n-1)*(y+z) + z，即 x - z = (n-1) * (y + z)
从 x-z 表达式可以看出，如果有两个指针同时从头结点，相遇结点这两个地方出发，它们肯定会在环形入口相遇。因为它**们之间的差值刚好是圆环长度的整数倍（**更加严格一点的证明可以用数学归纳法）。
经过数学证明，我们可以写出求解代码如下（解析在注释里）：
java
public class Solution {
public ListNode detectCycle(ListNode head) {
// 这里都是判断链表是否存在环
if (head == null || head.next == null) {
return null;
}
ListNode s1 = head;
ListNode s2 = head;
while (s2 != null && s2.next != null) {
s1 = s1.next;
s2 = s2.next.next;
if (s1 == s2) {
break;
}
}
// 当不存在链表环的时候，直接返回null
if (s1 != s2) {
return null;
}
// s1指针重新指向链表head，从head出发
s1 = head;
// s2指针此时位于相遇的位置
// 然后两个指针一起走
while (s1 != s2) {
s1 = s1.next;
s2 = s2.next;
}
// 返回环形的入口结点
return s1;
}
}复杂度分析：时间复杂度为 O(N)，空间复杂度为 O(1)。
总结与延伸
经过这两讲的学习，你终于可以用这三板斧来毒打链表题了，在抄家伙之前，我们一起回想下每招式的作用吧。
第一斧：假头。假头的作用主要是避免关于空链表的判断与讨论，假头还可以用来避免检查前驱结点为空的情况。
第二斧：新链表。新链表的引入是为了解决在旧链表中进行原地的交换、插入、删除，把复杂的操作变成在新链表中头部插入或者尾部添加。
第三斧：双指针。双指针主要是用于寻找链表中的特定结点，双指针的走法可以一次一步，可以有快有慢，出发点也可以有前有后。
了解了思路，你还需要深入理解操作的代码模板，然后就可以成功地进行解题实战了。这里我已经为你总结好了《链表题通关路线图》，请参照此地图来通关链表题吧。
链表操作是很多其他复杂算法的基础，需要你熟练掌握，比如 LRU，跳表等数据结构里面都会用到链表。希望你课后能熟练地运行本讲介绍的思路。
此外，从算法的难度上来说，实际上链表题并不算太难，但是非常考验基本功。我在处理链表题时，经常把文中介绍的题目作为模板深刻理解，达到熟练记忆的程度。我希望你在理解解题思路的基础上，也能够熟练记忆这些模板，逐渐建立一个系统的知识体系。
思考题
最后，我再给你留一道思考题。
链表排序：给定一个单向链表，如何给这个链表排序，要求复杂度达到 O(nlogn)。
你能使用所讲的创建新链表 + 快排的思想吗？
你能使用快慢指针 + 合并排序的思想来解决吗？
学会了链表的三板斧，处理链表问题，变得越来越容易了。不过我们可不能总是待在舒适区，还有很多算法与数结构等着我们去征服。下一讲将介绍 06 | 树：如何深度运用树的遍历？记得按时来探险。