Linked List Cycle II -- LeetCode

原題鏈接: http://oj.leetcode.com/problems/linked-list-cycle-ii/
這道題是Linked List Cycle的擴展，就是在確定是否有cycle之後還要返回cycle的起始點的位置。從Linked List Cycle中用的方法我們可以得知a=kc-b（不了解的朋友可以先看看Linked List Cycle）。現在假設有兩個結點，一個從鏈表頭出發，一個從b點出發，經過a步之後，第一個結點會到達cycle的出發點，而第二個結點會走過kc-b，加上原來的b剛好也會停在cycle的起始點。如此我們就可以設立兩個指針，以相同速度前進知道相遇，而相遇點就是cycle的起始點。算法的時間復雜度是O(n+a)=O(2n)=O(n)，先走一次確定cycle的存在性並且走到b點，然後走a步找到cycle的起始點。空間復雜度仍是O(1)。代碼如下：

public ListNode detectCycle(ListNode head)
{
    if(head == null || head.next == null)
        return null;
    ListNode walker = head.next;
    ListNode runner = head.next.next;
    while(runner!=null && walker!=runner)
    {
        walker = walker.next;
        if(runner.next!=null)
            runner = runner.next.next;
        else
            runner = null;
    }
    if(runner == null)
        return null;
    runner = head;
    while(walker!=runner)
    {
        walker = walker.next;
        runner = runner.next;
    }
    return walker;
}