[leetcode]Linked List Cycle II-找链表环起始点（修正版）java

很多网上的算法指根据结论倒推出a=c这样的结论，是错误的！

这道题比较注重数学推到，

 如图，设置快慢两个指针，快指针的速度是慢指针的两倍

假设两个指针在z点相遇,那么快指针所走过的距离是慢指针的两倍

那么有以下公式，其中n代表快指针在环内转了n圈后行走b距离与慢指针相遇

2*(a+b)= a + b + n*(b+c)  ====> a = (n-1)(b+c) + c

由这个推到结果可以知道，a的长度为n-1个环的长度加上c的长度

那么得出结论，相遇后，慢指针从链表头重新开始，快指针的速度和满指针一样继续前行，必然会在Y点相遇，相遇时快指针可能已经沿环转了多圈

 

 

package leetCode;

/**
 * User: FR
 * Time: 10/28/14 1:35 PM
 * Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
 * Follow up:
 * Can you solve it without using extra space?
 */
public class LinkedListCycle2 {
    public ListNode detectCycle(ListNode head) {
        if(head == null){
            return null;
        }
        ListNode slow = head;
        ListNode fast = head.next;
        while (fast != null){
            if(slow == fast){
                slow = head;
                fast = fast.next;
                while (slow != fast){
                    slow = slow.next;
                    fast = fast.next;
                }
                return slow;
            }
            slow = slow.next;
            fast = fast.next;
            if(fast != null){
                fast = fast.next;
            }
        }
        return null;
    }

    class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }

    public static void main(String[] args){
        LinkedListCycle2 linkedListCycle = new LinkedListCycle2();
        ListNode node1 = linkedListCycle.new ListNode(1);
        ListNode node2 = linkedListCycle.new ListNode(2);
        ListNode node3 = linkedListCycle.new ListNode(3);
        ListNode node4 = linkedListCycle.new ListNode(4);
        ListNode node5 = linkedListCycle.new ListNode(5);
        ListNode node6 = linkedListCycle.new ListNode(6);

        node1.next = node2;
        node2.next=node3;
        node3.next=node4;
        node4.next=node5;
        node5.next=node6;
        node6.next=node2;
        System.out.println(linkedListCycle.detectCycle(node1).val);
    }
}