LeetCode 142. 环形链表 II

• 题目描述
• 题目分析
• • 关于环形链表
  • 关于入环口
  • 算法分析
• 总结

题目描述

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 n u l l null null。

为了表示给定链表中的环，我们使用整数 p o s pos pos 来表示链表尾连接到链表中的位置（索引从 0 0 0 开始）。 如果 p o s pos pos 是 − 1 -1 −1，则在该链表中没有环。注意， p o s pos pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。

示例 1：

输入： h e a d = [ 3 , 2 , 0 , − 4 ] , p o s = 1 head = [3,2,0,-4], pos = 1 head=[3,2,0,−4],pos=1
输出：返回索引为 1 1 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入： h e a d = [ 1 , 2 ] , p o s = 0 head = [1,2], pos = 0 head=[1,2],pos=0
输出：返回索引为 0 0 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入： h e a d = [ 1 ] , p o s = − 1 head = [1], pos = -1 head=[1],pos=−1
输出：返回 n u l l null null
解释：链表中没有环。

提示：

链表中节点的数目范围在范围 [ 0 , 104 ] [0, 104] [0,104] 内
− 105 < = N o d e . v a l < = 105 -105 <= Node.val <= 105 −105<=Node.val<=105
p o s pos pos 的值为 − 1 -1 −1 或者链表中的一个有效索引

题目分析

关于环形链表

首先我们一般接触的链表是单链表有表尾，并且表尾结点的 n e x t next next 指针域是指向 N U L L NULL NULL 的。

那么如何判断一个链表是否有环呢？我们可以现从生活的一个例子来思考：

假设有 A A A 同学和 B B B 同学在操场上跑步，如果他们跑的都是直道，并且 B B B 同学的跑步速度大于 A A A 同学的跑步速度，那么在到达终点之前，他们两个都不可能相遇。

但是，如果是在环形跑道上跑步的话，那么 A A A 同学和 B B B 同学同时开始跑的时候，总有一个时刻， A A A 和 B B B 同学会相遇，并且 B B B 同学比 A A A 同学多跑了整数圈（具体整数多少取决于 B B B 同学的跑步速度）

对于链表来说，我们可以先设置两个指针指向头指针指向的结点，然后一个指针是快指针，一个指针是慢指针，它们分别代表 B B B 同学和 A A A 同学。然后我们设置快指针的速度是每次移动两个结点，而慢指针的速度是每次移动一个结点，也就代表了快指针的移动速度大于慢指针。

1. 当链表没有环的时候，快指针一定会首先到达表尾或者是 N U L L NULL NULL 就好像上图直道跑步中， B B B 同学首先到达终点一样。
2. 当链表有环的时候，那么根据上面的分析，快指针和慢指针一定会在某一个结点相遇，指向同一个结点，就像上图分析弯道跑步一样会在某一个时刻相遇。
   
   

关于入环口

假设有 A A A 同学和 B B B 同学从起点开始跑步，然后他们在首次相遇点相遇，如下图所示：

我们假设：

1. 起点到入环口的距离为 D D D.
2. 入环口到首次相遇点的距离为 S 1 S_1 S1​.
3. 首次相遇点到入环口的距离为 S 2 S_2 S2​.

又因为当 A A A 同学和 B B B 同学第一次相遇的时候，他们所经过的时间是相同的，而且 B B B 同学多跑了 n n n 圈 ( n ≥ 1 ) (n\ge1) (n≥1)
又因为 V B = 2 V_B = 2 VB​=2 , V A = 1 V_A = 1 VA​=1,所以可以得出以下等式成立：

经过整理得：

以上表达式可以告诉我们：

1. 如果 A A A 同学从起点开始走， B B B 同学从首次相遇点开始走，并且他们的速度都是匀速的。
2. 当 B B B 同学走了 S 2 S_2 S2​距离到达入环口的时候， A A A 同学也走了 S 2 S_2 S2​ 距离，而且 A A A 同学还剩 ( D − S 2 ) (D-S_2) (D−S2​) 距离，根据以上等式也就是 ( n − 1 ) ( S 1 + S 2 ) (n-1)(S_1+S_2) (n−1)(S1​+S2​) 的距离。
3. 所以当 A A A 同学继续往前走到达入环口的时候， B B B 同学一定从入环口走 ( n − 1 ) ( S 1 + S 2 ) (n-1)(S_1+S_2) (n−1)(S1​+S2​) 的距离再次到达入环口。因此这两个同学就在入环口相遇了。

算法分析

根据以上两个讨论，我们可以总结归纳出以下的算法：

1. 首先用 f a s t fast fast 指针和 s l o w slow slow 指针都指向 h e a d head head 指向的第一个结点
2. 每一次都判断 f a s t fast fast -> n e x t next next 和 f a s t fast fast 是否为 n u l l null null 值，如果判断是的话，则说明判断的链表是无环链表。
3. 当 f a s t fast fast 指针和 s l o w slow slow 指针相等的时候，则说明他们两个指针指向同一个结点，则说明有环、
4. 将 f a s t fast fast 指针指向首结点，把步长速度从 2 2 2 调整为 1 1 1 并且让 f a s t fast fast 指针和 s l o w slow slow 指针同时往后移动
5. 等到他们再次相遇的时候，他们所指向的结点一定是入环口

代码如下：

/**
 1. Definition for singly-linked list.
 2. struct ListNode {
 3.     int val;
 4.     struct ListNode *next;
 5. };
 */
struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode* fast = head;
    struct ListNode* slow = head;//让fast和slow都指向首结点
    while(1)//循环操作
    {
        if(fast == NULL || fast->next == NULL)
            return NULL;//当fast或者是fast->next指向空时，说明不是环形链表
            fast = fast->next->next;//fast的步长为2
            slow = slow->next;//slow的步长为1
        if(fast == slow)
            break;//当fast和slow相遇的时候，则不用继续往下走了，跳出while循环
    }
    fast = head;//把fast回到起点，slow在首次相遇点
    while(fast!=slow)//当fast和slow没有相遇的时候，以相同速度往前走
    {
        fast = fast->next;
        slow = slow->next;//步长都为1
    }
    return fast;//return slow也可以，因为他们相遇了
}

总结

1. 如何判断有环和无环要清晰
2. 算法问题要学会抽象化为数学问题求解