力扣142.環形連結清單II(快慢指針）

力扣刷題記錄

問題描述：

給定一個連結清單，傳回連結清單開始入環的第一個節點。 如果連結清單無環，則傳回 null。

為了表示給定連結清單中的環，我們使用整數 pos 來表示連結清單尾連接配接到連結清單中的位置（索引從 0 開始）。 如果 pos 是 -1，則在該連結清單中沒有環。注意，pos 僅僅是用于辨別環的情況，并不會作為參數傳遞到函數中。

遇到環路問題就要想到快慢指針，類似國小的跑圈問題

一、快慢指針：

定義一個fast指針，一個slow指針，fast每次走兩步，slow每次走一步，如果沒有環路，fast指針一定會指空；如果有環路，兩個指針一定會相遇

設slow走了x步，fast走了2x步，環路節點數為n，環路開始之前節點數為k。

相遇時滿足2x-k-n=x-k，則x=n，剛好為環路的節點數，若此時slow再走k步則回到環路開始結點，是以使fast指針回到最開始的結點，fast再走k步也會到達環路開始結點，兩指針都以1的速度走，相遇的節點即為環路的開始點。

二、代碼如下：

/**
 * 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,*slow;
        fast=head;
        slow=head;
        //判斷是否為環路
        while(fast!=NULL){
            fast=fast->next;
            slow=slow->next;
            if(fast!=NULL){
                fast=fast->next;
                if(fast==slow) break;
            }
        }
        if(fast==NULL) return NULL;//無環路
        fast=head;//快指針回到起點
        //找環路起點
        while(fast!=slow){
            fast=fast->next;
            slow=slow->next;
        }
        return fast;
    }
};