LeetCode142 环形链表 II

前言

题目： 142. 环形链表 II
文档： 代码随想录——环形链表 II
编程语言： C++
解题状态： 思路错误，链表不允许被修改

思路

两步走，第一步，判断有没有环，第二步，判断入环口在哪边。

代码

快慢指针法

• 第一步

  定义两个指针，一个快指针，一个慢指针。快指针每次平移两个，慢指针每次平移一个。如果两个指针可以相遇，就代表有环。在一个环内，快速的移动肯定会经过慢速的移动

• 第二步

  在两个指针的相遇处，令头节点和相遇节点相向而行，两个指针必定会相遇，并且相遇点就是环的入口。数学推理可见代码随想录讲解。

/**
 * 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* fast = head;
        ListNode* slow = head;

        while (fast != NULL && fast -> next != NULL) {
            fast = fast -> next -> next;
            slow = slow -> next;
            if (fast == slow) {
                ListNode* index1 = fast;
                ListNode* index2 = head;
                while (index1 != index2) {
                    index1 = index1 -> next;
                    index2 = index2 -> next;
                }
                return index1;
            }
        }
        return NULL;
    }
};
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

• 时间复杂度： $O(n)$
• 空间复杂度： $O(1)$