跳转至

142. 环形链表 II

力扣链接(中等)：https://leetcode.cn/problems/linked-list-cycle-ii

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

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。

示例 1：

img

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

示例 2：

img

Text Only
1
2
3
输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

img

Text Only
1
2
3
输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。

提示：

  • 链表中节点的数目范围在范围 [0, 104] 内
  • -10^5 <= Node.val <= 10^5
  • pos 的值为 -1 或者链表中的一个有效索引

进阶：你是否可以使用 O(1) 空间解决此题？

个人题解

常规解法：哈希表

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        unordered_set<ListNode *> set;
        while(head && set.find(head) == set.end()){
            set.insert(head);
            head = head->next;
        }
        return head;
    }
};

双指针

空间复杂度：\(O(1)\)

C++
 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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode *slow = head, *fast = head;
        if(!head || !head->next) return NULL;

        // 由于 fast 每次走两步，必须要判断 fast->next
        while(fast && fast->next) {
            slow = slow->next; fast = fast->next->next;
            // 此时相遇
            if(slow == fast) {
                ListNode *node = head;
                // 能相遇就代表已经有环了，永远不可能走到空指针
                // 所以不用判断是否为 null 
                while(node != slow){
                    node = node->next;
                    slow = slow->next;
                } 
                return node;
            }
        }
        return NULL;
    }
};

具体数学推导：

fig1

如图所示，快慢指针总会在环中某个位置相遇，因为慢指针要和快指针相遇，那么快指针至少会比慢指针多走一圈才有可能相遇，即快指针移动：\(a + n(b + c) + b \quad (n >= 1)\)。

又因为，对于环形链表问题，通常我们让快指针速度是慢指针的两倍，那么相同移动时间下就有：\(2(a + b) = a + n(b + c) + b\)。

找入环的第一个节点，本质就是求 \(a\)，那么可以对上述等式变形：

\[ \begin{align*} 2(a + b) &= a + n(b + c) + b\\ a &= n(b + c) - b\\ a &= (n - 1)(b + c) + c \end{align*} \]

我们会发现：从相遇点到入环点的距离加上 \(n−1\) 圈的环长，恰好等于从链表头部到入环点的距离。

由于当前我们已经找到了第一个相遇点，所以只需要新建一个指针指向链表头部，和在第一个相遇点的慢指针一起向后移动，当慢指针移动 \((n - 1)(b + c) + c\) 时，就找到入环点了。