Linked List Cycle II

题目

找Linked List cycle的起始位置(然后remove cycle，这个leetcode上没有，自己给自己加戏..)

答案

Why slow pointer/ fast pointer methods work?
Two pointers running in a cycle, you will always end up two situations:
First: f s
Second: f _ s
In the first situation, it takes 1 more step for them to meet.
In the second situation, it takes 2 more steps for them to meet.
So.... it works!

Let's define some variable in the linked list with cycle.
m: distance from head of list to start of cycle
k: distance from start of cycle to where the fast and slow pointer will eventually meet.
P: how many times the fast pointer went through the cycle
Q: how many times the slow pointer went through the cycle
C: length of the cycle
If the fast pointer and slow pointer arrive at the same point in the cycle, this equation will be true:
m + PC + k = 2(m + QC + k)
=> m+k = C(P-2Q)

Now, if you look at the below picture. If we start out from the start of cycle and go k steps, and then go m more steps, we will arrive at the start of the cycle again(because m+k is proved to be a multiple of cycle length).

We can use this to find out exactly where is the start of the cycle:
ptr1 = head of list
ptr2 = meeting point in the cycle
Both pointers march forward, if we see ptr1==ptr2, then we have met the start of the cycle!

Screen Shot 2018-10-14 at 4.17.46 PM.png

public ListNode nodeInCycle(ListNode head) {

       if(head == null) return null;

       ListNode fast = head, slow = head;

       while(fast != null && fast.next != null) {

           fast = fast.next.next;

           slow = slow.next;

           if(fast == slow)  return fast;

       }

       return null;

   }

public ListNode detectCycle(ListNode head) {

       ListNode p = nodeInCycle(head);

       if(p == null) return null;

       ListNode q = head;

       while(p != q) {

           p = p.next;

           q = q.next;

       }

       return p;

   }

public void removeCycle(ListNode head) {

       ListNode p = nodeInCycle(head);

       if(p == null) return null;

       ListNode q = head;

       while(p.next != q) {

           p = p.next;

           q = q.next;

       }

       p.next = null;

   }**