Linked List Cycle II

Question

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Example Given -21->10->4->5, tail connects to node index 1，返回10

Challenge Follow up: Can you solve it without using extra space?

Thoughts

可以先用1的解法看是否有cycle

[参考]（http://leetcode.tanglei.name/content/list/Linked-List-Cycle-II.html） 现在如果有cycle,来分析相遇的情况 假如有如下的list:

s-------a->-------
        |        |
        |-<-c----|

将这个list分位3段

• s->a = a
• a->c = b
• c->a = c

cycle的长度为b+c

第一次相遇时 fast走了 a + b + n(b+c) (n>=1) slow走了 a + b 那么

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

那么在第一次相遇后把fast换到head,并且两个指针都一步一步走，当fast走到a点时， slow也正好走到a点，(n-1)(b+c)是整数个圈 所以第二次相遇的点就是cycle的起点

Solution