Linked List Cycle II Show result

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

Have you met this question in a real interview? 

Yes

Example

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

Challenge

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

这道题目今天刚听一个小师弟提起来，我refer他来面试，组里面他的人问他了这个题的变种，如何数出带环的linked list的长度。

他给出的答案是，在node里加一个flag, visited， 来检测，o(n)的时间和近似为无的空间复杂度，但是不是一个好的解，因为要改掉node 的定义。

问他组里那个人给的啥，他说告诉他用set存指针，一旦碰到collision就停止， 其实这个复杂度变成了o(n^3)的复杂度 1^2+2^2+3^2.。。有公式可以算的，另外加上额外的o(n)的空间开销。 我笑了好久，这真是个坑爹的解。 

师弟问我我怎么解，首先我说在允许额外空间的时候，不二法宝是hash table, 哈希来检测碰撞就可以把复杂度降到 o(n)，但是额外空间的开销还是o(n), 其实还要大些，背景hash table 还是会多出很大来做bucket.

然后我就跟他讲了有这么道题，不用额外空间求解。

快慢指针：

慢指针走一步，快指针走两步，

那么有环而相遇, 假设重叠位置为距离为A， 相遇距离重叠位置距离为B，继续走C到重叠

那么相遇的时候，快指针走了A+2B+C， 慢指针走了A+B,因为快指针是慢指针的两倍速度，所以

A+2B+C=2A+2B -> A=C。那么让头指针和慢指针继续走，直到相遇，就是他们的交错点，如果求长度，

记录头指针和慢指针的和为长

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40

/** * Definition of ListNode * class ListNode { * public: * int val; * ListNode *next; * ListNode(int val) { * this->val = val; * this->next = NULL; * } * } */ class Solution { public: /** * @param head: The first node of linked list. * @return: The node where the cycle begins. * if there is no cycle, return null */ ListNode *detectCycle(ListNode *head) { // write your code here if(!head || !head->next) return 0; ListNode* slow=head->next; ListNode* fast= head->next->next; while(fast && fast->next){ if (slow==fast) break; slow=slow->next; fast=fast->next->next; } if (slow!=fast) return 0; while(head!=slow){ head=head->next; slow=slow->next; } return head; } };