LinkLists 找链表环入口 @CareerCup

原文：

Given a circular linked list, implement an algorithm which returns node at the beginning of the loop.

DEFINITION

Circular linked list: A (corrupt) linked list in which a node’s next pointer points to an earlier node, so as to make a loop in the linked list.

EXAMPLE

Input: A -> B -> C -> D -> E -> C [the same C as earlier]

Output: C

译文：

给定一个循环链表，实现一个算法返回这个环的开始结点。

定义：

循环链表：链表中一个结点的指针指向先前已经出现的结点，导致链表中出现环。

例子：

输入：A -> B -> C -> D -> E -> C [结点C在之前已经出现过]

输出：结点C

同http://blog.csdn.net/fightforyourdream/article/details/14639657

思路就不说了，有几点说明：

1）在快指针追击慢指针时，如何保证快指针不会跨过慢指针而不会重合？

快指针总是能和慢指针重合，为什么？因为如果假如真的“跨过了”，那么慢指针在i位置，快指针在i+1位置。但是考虑上一步，慢指针必定在i-1位置，快指针也在i-1位置，所以在上一步时已经重合了！

2）为什么相遇时通过重置慢指针，然后让快慢指针以相同速度前进，再次相遇就是环的开始点？

这就要分析一下走的过程了。因为快指针走的速度是慢指针的两倍，那么如果慢指针走p步，则快指针走了2p步。现在假设环的开始节点距离head节点有k个距离，则当慢指针走了k步时，慢指针正好到环的开始节点D，与此同时，快指针也走了2k步，前k步走在环外，后k步走在环内。由于k可能比环的长度还大，所以我们让k = k % LOOP_SIZE。

现在有如下的结论：

- 慢指针在环的开始处

- 快指针在超前环k步的位置上

- 慢指针落后k步于快指针

- 快指针落后 LOOP_SIZE - k 步于慢指针！

- 快指针以慢指针2倍的速度追击慢指针。或者说快指针以1步的相对速度追击相对静止的慢指针。则需要LOOP_SIZE-k 才能追上慢指针。在I位置追上。

D -> I 的距离是 LOOP_SIZE - k， I -> D 的距离是k，这段距离恰好和A->D的距离相同，都是k ！！！那么把慢指针放在head节点A，然后两个指针以相同速度前进，相遇处就是环的开始节点。

3）一个推论：快慢指针第一次相遇的地方和head的距离是环长度的整数倍。

假设相遇处离环开始点相距x个点，环长度为n个点
慢指针:k+qn+x=m (1)
又有2m-m=m=pn (2)
有(1),(2)可得:k+qn+x=pn
所以k+x = (p-q)n，即相遇处离head的距离为环长的整数倍.
所以将其中一个指针移至head，同时两指针以相同速度再次相遇即为环的开始处.

package LinkLists;

import CtCILibrary.LinkedListNode;

public class S2_6 {

	public static void main(String[] args) {  
		  
    }  
  
    public LinkedListNode detectCycle(LinkedListNode head) {  
        if(head == null || head.next ==null){  
            return null;  
        }  
        LinkedListNode slow = head;  
        LinkedListNode fast = head;  
          
        // 找到第一次相遇点  
        while(fast!=null && fast.next!=null && slow!=null){  
            slow = slow.next;  
            fast = fast.next.next;  
            if(slow == fast){       // 相遇  
                break;  
            }  
        }  
          
        // 检查是否因为有环退出或是因为碰到null而退出  
        if(slow==null || fast==null || fast.next==null){  
            return null;  
        }  
          
        // 把慢指针移到链表头，然后保持快慢指针同样的速度移动  
        // 再次相遇时即为环的入口  
        slow = head;  
        while(slow != fast){  
            slow = slow.next;  
            fast = fast.next;  
        }  
          
        // 现在快慢指针都指向环的入口  
        return slow;  
    }  
}