leetcode解題：(Medium) 142. Linked List Cycle II

題目：https://leetcode.com/problems/linked-list-cycle-ii/

描述：給定一個鏈結串列，找出串列中迴圈(cycle)開始的node，如果沒有迴圈則回傳null

解題思路：跟141一樣的找迴圈問題，但需要找到迴圈開始的node讓問題變複雜多了。假設用原本的2個快慢pointer方法，最後2個pointer會在圖中2的node上碰面，但我們要找的是圖中1的node

這時慢的pointer走了x+a的步數，快的pointer則走了x+2a+b的步數，由快的比慢的走多一倍步數可以得到2(x+a)=x+2a+b，稍微化簡後就能得出x=b，只要從head走b的步數就能找到1的所在位置了。這時就那麼剛好，從2個pointer碰面的node 2再走b步也會走到node 1的位置，換言之，只要在2個pointer碰面後，讓1個pointer從head開始每次走1格，另1個pointer繼續從node 2位置也每次走1格，這2個pointer下次碰面的位置就會剛好是迴圈開始的node 1了

程式碼：

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        if(head == null || head.next == null) return null;

        ListNode node1 = head;
        ListNode node2 = head;
        while(node2 != null && node2.next != null) {
            node1 = node1.next;
            node2 = node2.next.next;
            if(node1 == node2) break;
        }

        if(node1 != node2) return null;
        
        node1 = head;
        while(node1 != node2) {
            node1 = node1.next;
            node2 = node2.next;
        }

        return node1;
    }
}

時間複雜度：O(n)
空間複雜度：O(1)

tags: leetcode medium linked list two pointer