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;
}

这道题目更多的是数学上相遇点的推导，有了理论基础之后就是比较简单的链表操作。