在上一讲中，我给你介绍了解决链表问题的“三板斧”中的第一斧：假头，你知道了带假头的链表一共有 6 种基本的操作，分别是初始化、追加结点、头部插入结点、查找结点、插入指定位置之前和删除结点。

如果说三板斧的第一斧平平淡淡，大巧不工；第二斧就是鬼斧神工，生成新链表后，链表的交换、反转求解都会变得极其简单 ；第三斧则是奇思妙想，双指针（也叫快慢指针）用在链表上经常可以解决一些单个指针难以解决的问题。学会了这两种思路，算法面试中的链表题就如同探囊取物了。

注：大部分链表题主要考查动手能力，因此在本讲将不再按照“分析四步法”进行讲解。

三板斧的第二斧：新链表

做链表的反转、交换等操作时，我不建议直接在原来的链表上进行操作。一种可取的思路是，把这些操作想象成要生成新的链表，然后借助这些新的链表，完成原本比较复杂的操作。这个方法就是我们今天要讲的**“第二斧”——新链表**。

接下来，我将采用这种新思路，带你解决一些面试中经常会遇到的疑难题目。

例 1：链表反转

【题目】输入一个链表的头结点，反转该链表，并返回反转后链表的头结点。

输入：1->2->3

输出：3->2->1

【分析】这里借助假头和新链表求解，思路如下：

建立一个新的带假头的空链表；

遍历旧链表，依次取出旧链表中的每个结点；

采用头部插入的方法放到新链表中；

返回 dummy.next。

【画图】这里我们利用示意图演示如下：

【代码】对应的代码如下（解析在注释里）：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

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;
    }
}

代码：Java/C++/Python

复杂度分析：每个结点只遍历一次，所以时间复杂度为 O(N)，内存空间只使用了常量空间，因此空间复杂度为 O(1)。

【小结】仔细查看代码之后，链表反转的考点就是之前我们学到的基本操作：假头，头部插入法，再结合今天学习的新链表的思路。可以总结如下：

例 2：删除结点

【题目】给定一个链表头及一个整数值，要求把链表里面等于整数值的结点都从链表中移除出去。

输入：1->2->3->2->4, remove = 2

输出：1->3->4。

解释：要移除的整数值是 2。那么移除之后，返回的结果应该是 1->3->4。

【分析】这里我们不采用在原来的链表上进行删除的办法，而是采用新链表的操作思路：

建立一个新的带假头的空链表；

遍历旧链表，依次取出旧链表中的每个点，如果不删除这个结点，那么就采用尾部插入方法接到新链表中。

可以发现，在这里没有出现结点交换的操作。采用新链表的思路，避免了在原链表上不停地做结点的删除。为了方便你理解，我制作了动图演示，如下所示：

【代码】基于以上思想，可以写出代码如下（解析在注释里）：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

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;
    }
}

代码：Java/C++/Python

复杂度分析：时间复杂度 O(N)，空间复杂度 O(1)。

【小结】我们将这道题的考点层层剥离之后，就只剩下生成 dummy 新链表，尾巴追加新结点，以及新链表的思路。关于解决这道这类题目的思路、重点以及分析方法，建议你先尝试自己梳理总结，再来看我给出的思维导图：

如果我们仔细对比链表反转与删除结点，会发现，这两者的不同之处在于：

链表反转使用的是头部插入的方法

删除结点采用的是尾部追加的方法

只是换了一个考点，题目就完全大变样了。如果我们再严格地对比这两个题目，可以发现：

链表反转时，头部插入是无条件的

删除结点时，尾部 append 是有条件的

这种条件的千变万化，会带来很多有趣的题目。比如下面这道练习题。

练习题 1：给定一个排序链表，删除重复出现的元素，使得每个元素只出现一次。

输入: 1->1->2->3->3

输出: 1->2->3

代码：Java/C++/Python

练习题 2：给定一个排序链表，删除重复出现的元素，只留下没有重复出现的元素。

输入：1->1->2->3->3

输出：2

代码：Java/C++/Python

你可以把答案或者思考的过程写在评论区，我们一起讨论。

例 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。

具体演示如下所示：

【代码】有了前面的思路，可以写出代码如下（解析在注释里）：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

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;
    }
}

代码：Java/C++/Python

复杂度分析：时间复杂度 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]

代码：Java/C++/Python

你可以把答案或者思考的过程写在评论区，我们一起讨论。

例 4：交换链表中的结点

【题目】给定一个链表，需要将里面的结点两两交换。

输入：[1->2->3->4->5->6]

输出：[2->1->4->3->6->5]

【分析】经过观察发现，只不过把偶数位置与奇数位置的结点进行了交换。为了避免在原始链表中进行结点间的交换操作，我们可以采用如下方法：

生成两个新链表，一个用来存放奇数位置结点的链表 odd，一个用来存放偶数位置结点的链表 even；

遍历旧链表，并且把奇数位置上的结点放到 odd 链表中，把偶数位置的结点放到链表 even 中；

合并 odd 链表与 even 链表。

为了方便你理解，我同样制作了动图演示，如下：

到这里，新增链表已经从一条变成了两条，来帮助我们解决这道题目。

【代码】有了思路，我们可以写出代码如下（解析在注释里）：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

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);
    }
}

代码：Java/C++/Python

复杂度分析：每个结点会访问两次，拆分一次，合并一次，所以时间复杂度为 O(N)，空间复杂度为 O(1)。

【小结】这道题的考点也比较明确了，可以拆分出以下考点：

拆分链表

新链表的思路

合并链表的操作

尤其需要注意的是，使用新链表思路时，可以通过生成多条新链表来解决以前处理起来比较麻烦的问题。至此，我们一起进一步扩展了链表知识。此外，还发现了一些小型的组合操作，比如：**拆分链表，合并链表。**在合并时，如果按照不同的条件合并，就需要写出不一样的合并代码，结合前面例 3，可以知道合并分两种：

有序合并

先后合并

到这里可以总结出我们更加丰富的知识路线图，如下图所示：

在这道题中，链表是两两成对进行了反转，那么如果是 k 个一组进行反转应该怎么办呢？我们再来看看与交换有关的练习题。

练习题 4：给定一个链表，要求将链表 k 个一组进行反转，如果最后一组不足 k 个，那么不反转。返回反转之后的链表。

输入：A = [1, 2, 3, 4, 5], k = 2

输出: [2, 1, 4, 3, 5]

代码：Java/C++/Python

练习题 5：给定一个链表，从链表尾部开始，k 个一组进行反转，如果左边的分组不足 k 个，那么不反转。返回反转之后的链表。

输入：A = [1, 2, 3, 4, 5], k = 2

输出：[1, 3, 2, 5, 4]

解释：注意是从链表的尾部开始k个一组的。所以这里是[1], [2, 3], [4, 5]这样分组来进行反转。

代码：Java/C++/Python

三板斧的第三斧：双指针

虽然新链表的思路非常有趣，但是关于它的更多探索还是应该留给你自己。收拾好行囊，我们将要去看更加瑰丽的奇景——双指针。

双指针，顾名思义就是两个指针在链表上移动。实际上，我们在前面链表的查找中已经使用过双指针了：比如链表中指定位置插入一个新结点，就使用了两个指针，一前一后两个指针在链表上前进。

其实两个指针在链表上前进时，有很多种形式，常见的主要有以下两种。

间隔指针：前面的指针先走一步，然后后面的指针再一起走；前面的指针先走 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 非空，即指向倒数第一个结点。

【代码】有了思路以及相应的细节，我们就可以利用代码来解决问题了（解析在注释里）：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

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;
    }
}

代码：Java/C++/Python

复杂度分析：时间复杂度 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即可。

如果找到了中间结点，那么就可以直接进行拆分了。

【代码】接下来我们就实现拆分链表的逻辑，代码如下（解析在注释里）：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

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};
    }
}

代码：Java/C++/Python

复杂度分析：时间复杂度 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

代码：Java/C++/Python

例 7：链表环问题

【题目】给定一个链表，原本的链表尾巴如果不为空，并且指向了链表的中间结点，这样我们就认为这个链表存在一个环。给定一个链表，判断链表中是否存在环？

【分析】首先，如果链表中存在环，只用一个指针遍历肯定是永无止境的，这一个指针会在环里面打转。因此，我们可以再次利用双指针，s1，s2 两个指针都从链表头开始，s1 指针表示每次只往前走一步，s2 指针则是每次只往前走两步。那么链表最终只有两种情况：

1.s1 == s2，这个时候链表存在环；

2.s1 != s2，这个时候链表不存在环。

不过我们还是需要处理两种边界条件：

当为空链表的时候，s1 == s2，但是实际上此时链表无环；

当链表中只存在一个结点，并且无环的时候，运行的结果也会是 s1 == s2。

这两种边界条件的处理，只需要特殊判断一下即可。

【代码】有了前面了思路，那么我们就可以写出解问题的代码了（解析在注释里）：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

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;
    }
}

代码：Java/C++/Python

复杂度分析：时间复杂度为 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 表达式可以看出，如果有两个指针同时从头结点，相遇结点这两个地方出发，它们肯定会在环形入口相遇。因为它**们之间的差值刚好是圆环长度的整数倍（**更加严格一点的证明可以用数学归纳法）。

经过数学证明，我们可以写出求解代码如下（解析在注释里）：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

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;
    }
}

代码：Java/C++/Python

复杂度分析：时间复杂度为 O(N)，空间复杂度为 O(1)。

总结与延伸

经过这两讲的学习，你终于可以用这三板斧来毒打链表题了，在抄家伙之前，我们一起回想下每招式的作用吧。

第一斧：假头。假头的作用主要是避免关于空链表的判断与讨论，假头还可以用来避免检查前驱结点为空的情况。

第二斧：新链表。新链表的引入是为了解决在旧链表中进行原地的交换、插入、删除，把复杂的操作变成在新链表中头部插入或者尾部添加。

第三斧：双指针。双指针主要是用于寻找链表中的特定结点，双指针的走法可以一次一步，可以有快有慢，出发点也可以有前有后。

了解了思路，你还需要深入理解操作的代码模板，然后就可以成功地进行解题实战了。这里我已经为你总结好了《链表题通关路线图》，请参照此地图来通关链表题吧。

链表操作是很多其他复杂算法的基础，需要你熟练掌握，比如 LRU，跳表等数据结构里面都会用到链表。希望你课后能熟练地运行本讲介绍的思路。

此外，从算法的难度上来说，实际上链表题并不算太难，但是非常考验基本功。我在处理链表题时，经常把文中介绍的题目作为模板深刻理解，达到熟练记忆的程度。我希望你在理解解题思路的基础上，也能够熟练记忆这些模板，逐渐建立一个系统的知识体系。

思考题

最后，我再给你留一道思考题。

链表排序：给定一个单向链表，如何给这个链表排序，要求复杂度达到 O(nlogn)。

你能使用所讲的创建新链表 + 快排的思想吗？

你能使用快慢指针 + 合并排序的思想来解决吗？

解法 1：Java/C++/Python解法 2：Java/C++/Python

学会了链表的三板斧，处理链表问题，变得越来越容易了。不过我们可不能总是待在舒适区，还有很多算法与数结构等着我们去征服。下一讲将介绍 06 | 树：如何深度运用树的遍历？记得按时来探险。

-– ### 精选评论 ##### *明： > 德老师，总结的太到位了！回答一下合并k个有序链表的解题思路：（1）可以创建一个大小为 k 的 最小堆，先把所有链表的头部结点全部添加进去；（2）利用假头 dummy，初始化一个新链表，每次从最小堆中取出一个结点，即最小值，把它 append 到新链表的末尾；同时把该结点的下一个结点添加到 最小堆中（如果该结点的下一个结点不为空）。（3）返回 dummy. next。 ##### **4943： > 对于练习6的思考题：（1）由于增加了dummy节点作为假头，而s1和s2都是从head开始的，存在的两种特殊情况是head本身就是空节点和head.next为空节点，但是这两种情况都会由于pre的存在使得返回的mid就是pre,对应的分隔链表也就是正确的。（2）s1和s2从head开始就是为了不需要判断链表为空的情况；从dummy开始也是可以的，但是findMiddleNode方法里while的循环条件要改变，要改成s2.next != null s2.next.next != null,此时能同样解决（1）中提到的两种情况。如果分析的不对请老师指正 ######     讲师回复： >     不错哦。(2)可能还需要想一下。 （1）做个参考：https://github.com/lagoueduCol/Algorithm-Dryad/blob/main/05.LinkedList/splitList.2.java （2）做个参考：https://github.com/lagoueduCol/Algorithm-Dryad/blob/main/05.LinkedList/splitList.3.java ##### **伟： > tail.next=xxxtail=xxx老师，我这两行代码任是没有绕过弯来，不知道啥意思？😂 ######     讲师回复： >     你玩老鹰抓小鸡游戏，你去抓住排在最后一只小鸡的尾巴(tail.next = p)。 然后，你就变成了队伍里面的最后一只小鸡。tail = p; ##### **0960： > 链表中点的题目：如果使用dummy作为起始位置的话：奇数：最后front的节点是null，back走到了前半部分的最后一个，偶数：最后front的节点的next是null，back走到了前半部分的最后一个，所以没有必要区分 ######     讲师回复： >     赞！ ##### **8113： > 老师，请问 例2 ，// 注意设置尾巴的next为空 尾部移到最新的节点，下一个节点应该也是为null的，为啥要这一步的操作呢？ ######     讲师回复： >     并不是所有的题目都能够保证最后的这个尾巴是空的。这里补刀是要保证所有的链表你的屁股都是擦干净的。养成好习惯。^_^ ##### **健： > 有个细节问题，在cpp的链表删除代码里，是否要对删去的节点进行内存回收呢？ ######     讲师回复： >     在面试的时候，一定要记得写上！在leetcode里面，如果是自己new的，那么删除的时候就自己delete。如果不是自己new的，那么就不要动它。 ##### **亚： > 不太懂为什么s1重新赋值然后和s2一块走😂 ######     讲师回复： >     嗯。这里不要直接看代码，要先去看前面的那个数学上的证明。你可以想象成：你人在食堂。你室友在宿舍。你们约好一起去跑步（为什么要约室友去跑步，这个不重要！）。你们相约在操场入口碰头。假设你的路程更近（你们两个人移速一样！）先到了操场入口。然后你看你室友还没到。你就围着操场跑了起来。如果最后的跑的路程 - 室友走的路程 = 操场环形跑道的整数倍。 那么最后你和室友肯定是在操场入口相遇。而前面那一坨数学，就是在证明，这个路程就是圆环的整数倍。所以，你只需要保证移动速度一样就可以了。所以两个指针分别从各自的地方出发。然后再一步一步走。 s1指针就是你室友。s2指针就是你。你们移动速度一样。必然在操场入口碰头 ##### **帆： > 老师，关于新链表解题的空间复杂度是o(1)而不是o(n)是这样理解吗？我们虽然新建了一个链表，但链表中的每个节点只是原链表中对应节点的引用(并没有通过 new Node). ######     讲师回复： >     正解! ##### 周： > 老师您好，扩展题里找链表开始入环的第一个节点那题，快指针s2走过的路径长度是不是应该是b = x + y + n * (y + z) 呢？这样才能推导出: x - z = (n - 1)*(y + z) 呢。另外，老师真的是总结很好，感觉以后链表题都有思路了而不是无从下手，谢谢老师的讲解！！ ######     讲师回复： >     非常感谢你的指正。已更正 ##### **一郎： > 老师，这些题目都是从leetcode上面找的吧，下次能否把题目编号也给贴出来。 ######     编辑回复： >     在每一道题的git repo里面的链接，有完整的代码，以及相应的测试平台或者leetcode 链接。 ##### **7225： > 双指针方法找链表倒数第k个数，相当于第一个指针遍历所有节点，第二个只是少遍历k个，总起来来说不是遍历一遍列表啊 ######     讲师回复： >     遍历一遍与每个结点只访问一次是两个概念。并不是说每个结点只能访问一次！它的含义是指你只能从头到尾看一次。如果你先用while循环求出链表的长度，再一个while循环求倒数第k个。这样你遍历链表，你就遍历了两遍。