142. Linked List Cycle II

  • 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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
if(!head || !head->next) return NULL;
ListNode *fast = head;
ListNode *slow = head;
while(fast->next && fast->next->next){
fast = fast->next->next;
slow = slow->next;
if(fast==slow){
fast = head;
while(fast!=slow){
fast = fast->next;
slow = slow->next;
}
return slow;
}
}
return NULL;
}
};

https://discuss.leetcode.com/topic/5284/concise-o-n-solution-by-using-c-with-detailed-alogrithm-description

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
ListNode *detectCycle(ListNode *head) {
if (head == NULL || head->next == NULL)
return NULL;

ListNode *slow = head;
ListNode *fast = head;
ListNode *entry = head;

while (fast->next && fast->next->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) { // there is a cycle
while(slow != entry) { // found the entry location
slow = slow->next;
entry = entry->next;
}
return entry;
}
}
return NULL; // there has no cycle
}

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
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
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
if(head==NULL || head->next == NULL) return NULL;

ListNode* firstp = head;
ListNode* secondp = head;
bool isCycle = false;

while(firstp!=NULL && secondp!=NULL){
firstp = firstp->next;
if(secondp->next==NULL) return NULL;
secondp = secondp->next->next;
if(firstp==secondp){
isCycle = true;
break;
}
}

if(!isCycle) return NULL;
firstp = head;
while(firstp != secondp){
firstp = firstp->next;
secondp = secondp->next;
}
return firstp;
}
};


https://discuss.leetcode.com/topic/33191/c-implementation-with-much-more-clear-and-strict-explanation-any-one-can-give-more-clear

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
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
set the

[#cycle length = C ]

[#length-from-head-to-cycle-start-point = L]

[#cycle-start-point-meeting-point=S]

[#meeting-point-clock-direction-to-cycle-start-point=Y]

[#step needed to meeting=T]
Then when they meet, we have

2 * T = T + N1 * C N1=0,1,2...
so we get

T = N1 * C
Also we have

2 * T = L + N2 * C + S N2=0,1,2...
we can get

N3 * C = L + S with C = S + Y N3 = 2 * N1 - N2
so we have

(N3 - 1) * C + S + Y = L + S
then we have

(N3 - 1) * C + Y = L
just means that we can do the things that have been explained by others.

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
ListNode* dummy=new ListNode(-1);
dummy->next=head;
ListNode *slow=dummy, *fast=dummy;
bool flag=false;
while(fast && fast->next){
slow=slow->next;
fast=fast->next->next;
if(fast==slow) { flag=true; break; }
}
if(!flag) return NULL;
ListNode* result=dummy;
while(result != slow){
result=result->next;
slow=slow->next;**strong text**
}
return result;
}
};

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
2
3
4
5
6
7
8
H: distance from head to cycle entry E
D: distance from E to X
L: cycle length
_____
/ \
head_____H______E \
\ /
X_____/

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
# @param head, a ListNode
# @return a list node
def detectCycle(self, head):
try:
fast = head.next
slow = head
while fast is not slow:
fast = fast.next.next
slow = slow.next
except:
# if there is an exception, we reach the end and there is no cycle
return None

# since fast starts at head.next, we need to move slow one step forward
slow = slow.next
while head is not slow:
head = head.next
slow = slow.next

return head

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
2
3
4
5
6
7
8
9
10
11
12
13
def detectCycle(self, head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
break
else:
return None
while head != slow:
slow = slow.next
head = head.next
return 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
2
A+B+N = 2A+2B
N=A+B

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode slow = head;
ListNode fast = head;

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

if (fast == slow){
ListNode slow2 = head;
while (slow2 != slow){
slow = slow.next;
slow2 = slow2.next;
}
return slow;
}
}
return null;
}
}
谢谢你,可爱的朋友。