linkedListCycleII

142. 环形链表II

分析

判断链表是否有环
- 设置两个指针 slow 和 fast，初始都指向链表头节点 head
- 快指针每次移动两步，慢指针每次移动一步
- 如果快指针追上慢指针，说明链表中有环；否则，如果快指针或其下一节点为空，则链表无环
找到环的起始节点
- 当快慢指针相遇时，将慢指针重置为链表头节点 head
- 快指针保持在相遇位置
- 两个指针每次都向前移动一步，当两者再次相遇时，相遇点即为环的起始节点

数学推导

假设：

链表头到环入口节点的距离为 a
环入口到相遇点的距离为 b
相遇点到环入口的距离为 c

快指针比慢指针速度快一倍，因此：2(a + b) = a + b + n(b + c)（ n 为快指针在环中绕的圈数），化简得：a = c + (n - 1)(b + c)

这表明：

从链表头节点到环入口的距离 a 等于从相遇点沿环走回入口的距离 c
因此，当两个指针一个从链表头开始，一个从相遇点开始，每次移动一步，最终会在环的起始节点相遇

时间复杂度

快慢指针遍历链表一次即可确定是否有环，以及找到环的起始节点，时间复杂度 O(n)

空间复杂度

空间复杂度为 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
33
34
35


class Solution
{
public:
    ListNode *detectCycle(ListNode *head)
    {
        // 链表为空或只有一个节点，不可能有环
        if (!head || !head->next)
            return nullptr;

        ListNode *slow = head, *fast = head;

        // 判断链表是否有环
        while (fast)
        {
            slow = slow->next;          // 慢指针走一步
            fast = fast->next;          // 快指针走一步
            if (fast)
                fast = fast->next;      // 快指针再走一步

            if (slow == fast)           // 快慢指针相遇
            {
                // 找到环的起始节点
                slow = head;            // 慢指针回到链表头
                while (slow != fast)    // 两指针相遇即为环入口
                {
                    slow = slow->next;
                    fast = fast->next;
                }
                return fast;
            }
        }

        return nullptr; // 无环
    }
};