- 31.0%

https://leetcode.com/problems/linked-list-cycle-ii/?tab=Description

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

Note: Do not modify the linked list.

Follow up:

Can you solve it without using extra space?

方法一：

类似于141题，但是slow和fast相遇的地点并不是循环开始的地点。通过数学证明，可以知道，相遇点到循环开始点的距离与head到循环点的距离相等，从而找出。

1 | class Solution { |

Concise O(n) solution by using C++ with Detailed Alogrithm Description

Alogrithm Description:

Step 1: Determine whether there is a cycle

1.1. Using a slow pointer that move forward 1 step each time

1.2. Using a fast pointer that move forward 2 steps each time

1.3. If the slow pointer and fast pointer both point to the same location after several moving steps, there is a cycle;

1.4. Otherwise, if (fast->next == NULL || fast->next->next == NULL), there has no cycle.

Step 2: If there is a cycle, return the entry location of the cycle

2.1. L1 is defined as the distance between the head point and entry point

2.2. L2 is defined as the distance between the entry point and the meeting point

2.3. C is defined as the length of the cycle

2.4. n is defined as the travel times of the fast pointer around the cycle When the first encounter of the slow pointer and the fast pointer

- According to the definition of L1, L2 and C, we can obtain:
- the total distance of the slow pointer traveled when encounter is L1 + L2
- the total distance of the fast pointer traveled when encounter is L1 + L2 + n * C
- Because the total distance the fast pointer traveled is twice as the slow pointer, Thus:
- 2
*(L1+L2) = L1 + L2 + n*C => L1 + L2 = n*C => L1 = (n - 1) C + (C - L2)*

快指针不会超过慢指针好几圈，因为如果当前节点没有相遇，则下一个节点一定会相遇。

It can be concluded that the distance between the head location and entry location is equal to the distance between the meeting location and the entry location along the direction of forward movement.

So, when the slow pointer and the fast pointer encounter in the cycle, we can define a pointer “entry” that point to the head, this “entry” pointer moves one step each time so as the slow pointer. When this “entry” pointer and the slow pointer both point to the same location, this location is the node where the cycle begins.

Here is the code:

1 | ListNode *detectCycle(ListNode *head) { |

9ms, September 22, 2016

https://discuss.leetcode.com/topic/2975/o-n-solution-by-using-two-pointers-without-change-anything

O(n) solution by using two pointers without change anything

my solution is like this: using two pointers, one of them one step at a time. another pointer each take two steps. Suppose the first meet at step k,the length of the Cycle is r. so..2k-k=nr,k=nr

Now, the distance between the start node of list and the start node of cycle is s. the distance between the start of list and the first meeting node is k(the pointer which wake one step at a time waked k steps).the distance between the start node of cycle and the first meeting node is m, so…s=k-m,

s=nr-m=(n-1)r+(r-m),here we takes n = 1..so, using one pointer start from the start node of list, another pointer start from the first meeting node, all of them wake one step at a time, the first time they meeting each other is the start of the cycle.

1 | class Solution { |

C++ implementation with much more clear and strict explanation ! any one can give more clear ?

Just use the dummy head pointer and why first find the meeting point and then set the result-pointer at the dummy and move forward to find the result position.

There are the reasons :

1 | set the |

We can move a node from head and node from the meeting point, then when they meet, it is the

start point of the cycle.

Here is the code :

1 | class Solution { |

#### python

85ms, 51.12%, September 22, 2016

https://discuss.leetcode.com/topic/17521/share-my-python-solution-with-detailed-explanation

Share my python solution with detailed explanation

My solution consists of two parts. The first one checks if a cycle exists or not. The second one determines the entry of the cycle if it exists.

The first part is inspired by this post. about Linked List Cycle I

The logic behind the 2nd part is like this:

Consider the following linked list, where E is the cylce entry and X, the crossing point of fast and slow.

1 | H: distance from head to cycle entry E |

If fast and slow both start at head, when fast catches slow, slow has traveled H+D and fast 2(H+D).

Assume fast has traveled n loops in the cycle, we have:

2H + 2D = H + D + L –> H + D = nL –> H = nL - D

Thus if two pointers start from head and X, respectively, one first reaches E, the other also reaches E.

In my solution, since fast starts at head.next, we need to move slow one step forward in the beginning of part 2

1 | class Solution: |

https://discuss.leetcode.com/topic/5438/sharing-my-python-solution

Sharing my Python solution

Same idea as many other posts, just the python version:

1 | def detectCycle(self, head): |

#### java

1ms, September 22, 2016

https://discuss.leetcode.com/topic/19367/java-o-1-space-solution-with-detailed-explanation

Java O(1) space solution with detailed explanation.

Define two pointers slow and fast. Both start at head node, fast is twice as fast as slow. If it reaches the end it means there is no cycle, otherwise eventually it will eventually catch up to slow pointer somewhere in the cycle.

Let the distance from the first node to the the node where cycle begins be A, and let say the slow pointer travels travels A+B. The fast pointer must travel 2A+2B to catch up. The cycle size is N. Full cycle is also how much more fast pointer has traveled than slow pointer at meeting point.

1 | A+B+N = 2A+2B |

From our calculation slow pointer traveled exactly full cycle when it meets fast pointer, and since originally it travled A before starting on a cycle, it must travel A to reach the point where cycle begins! We can start another slow pointer at head node, and move both pointers until they meet at the beginning of a cycle.

1 | public class Solution { |