142. 环形链表 II

Introduction

Question：142. 环形链表 II

Analysis

用快慢指针就能解决掉了，快指针和慢指针以头结点为起点，快指针每次向前移动两个节点，慢指针每次向前移动一个节点。当快慢指针指向同一个节点时，链表有环。这个结论非常容易理解，相信两个人赛跑，第一个人比第二个人跑的快，只有赛道呈现环装，才可能出现两人相遇的情况。

而如何确定环入口就比较难理解了。

假设快指针走了 n 圈
快指针走过的距离：a + n ( b + c)
慢指针走过的距离：a + b

因此a+n(b+c)=2*(a+b)，则a = c + (n - 1)(b+c)。

所以在相遇后可以让慢指针继续向前走，同时让一个指针从头结点出发，同样的速度前进，当他们相遇时就是在环入口。

Implement

ListNode *detectCycle(ListNode *head) {
    if (head == nullptr || head->next == nullptr) return nullptr;
    ListNode* fast = head->next->next;
    ListNode* slow = head->next;
    while(fast && fast->next && fast != slow) {
        fast = fast->next->next;
        slow = slow->next;
    }
    if (fast == nullptr || fast->next == nullptr) return nullptr;
    while (slow!=head) {
        slow = slow->next;
        head = head->next;
    }
    return head;
}

Reference

• 官方题解