LeetCode141. Linked List Cycle

Easy

Given a linked list, determine if it has a cycle in it.

To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

Example 1:

1
2
3
Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the second node.

img

Example 2:

1
2
3
Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the first node.

img

Example 3:

1
2
3
Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.

img

Follow up:

Can you solve it using O(1) (i.e. constant) memory?

常数空间判断环。


思路

  • 快慢指针:判断是否有环,快慢指针相遇就有环;如果有环一定走不到null。

Mine in C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
bool hasCycle(ListNode *head) {
ListNode* fast,*slow;//1.
fast = slow = head;
while (fast&&fast->next)//2.
{
fast = fast->next->next;
slow = slow->next;

if (fast == slow)//3.
return true;
}
return false;
}
};

细节

  • 快慢指针。
  • fast&&fast->next一起判空。
  • 有环必走不到空,指针相遇就有环。

LC in Python

1
2
3
4
5
6
7
8
9
10
def hasCycle(self, head):
try:
slow = head
fast = head.next
while slow is not fast:
slow = slow.next
fast = fast.next.next
return True
except:
return False

ref:Except-ionally fast Python


Medium

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

To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

Note: Do not modify the linked list.

Example 1:

1
2
3
Input: head = [3,2,0,-4], pos = 1
Output: tail connects to node index 1
Explanation: There is a cycle in the linked list, where tail connects to the second node.

img

Example 2:

1
2
3
Input: head = [1,2], pos = 0
Output: tail connects to node index 0
Explanation: There is a cycle in the linked list, where tail connects to the first node.

img

Example 3:

1
2
3
Input: head = [1], pos = -1
Output: no cycle
Explanation: There is no cycle in the linked list.

img

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

没有额外空间找到入口节点。


思路

  • 在判断是否存在环时,计数记为n。
  • 快指针先走n个,两个指针相遇处为入口处。

Mine in 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
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
if (!hasCycle(head)) //2.
return nullptr;

ListNode* fast, *slow;
fast = slow = head;
while (count--)
{
fast = fast->next;
}
while (slow!=fast)
{
fast = fast->next;
slow = slow->next;
}
return slow;
}
bool hasCycle(ListNode *head) {
ListNode* fast, *slow;
fast = slow = head;
while (fast&&fast->next)
{
fast = fast->next->next;
slow = slow->next;
count++;//1.
if (fast == slow)
return true;
}
return false;
}

private:
int count = 0;
};

Follow up

没有额外空间找到入口节点。

  • No extra space (other than recursive stack),不能用递归,也不能用全局变量计数,用三个指针,环状检测算法。

环状检测算法描述

  • 确定是否有环

    1. slow走一步
    2. fast走两步
    3. 快慢指针相遇,则有环
    4. 否则 if (fast->next == NULL || fast->next->next == NULL),没有环
  • 如果有环,返回入口节点

    1. L1 :头节点 到 入口 的距离
    2. L2:相遇点 到 入口 的距离
    3. C : 环大小
    4. n : 当快慢指针第一次相遇时,fast 遍历过环的次数
  • 根据L1,L2,C的定义得到

    1. 相遇时,slow走的总路程: L1 + L2
    2. 相遇时,fast走的总路程:L1 + L2 + n * C
    3. 因为fast走的是slow的两倍:
      • 2 * (L1+L2) = L1 + L2 + n * C
      • L1 + L2 = n * C
      • L1 = (n - 1) C + (C - L2)
  • 由此推得:

    1. 快慢指针第一次相遇时,头节点和入口节点的距离=(沿着指针移动的方向,)相遇节点和入口节点的距离.L1 = (n - 1) C + (C - L2) ,这一步很关键!!! if (slow == fast){}
    2. 同时 入口指针 也开始和 slow指针 一样走动了,一次走一步。
    3. 当他们相遇时入口指针就指向入口节点。 return entry;

LC in C++

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) {// 1.
while(slow != entry) {// 2.
slow = slow->next;
entry = entry->next;
}
return entry;//3.
}
}
return NULL;
}

LC in Python

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

总结

  1. O(1)space.O(n)time
  2. 需要计数的方法:找入口节点分两步,第一检测是否有环:快慢指针相遇,并且计数;第二找到入口:快指针先走size步,相遇就是入口节点。
  3. 更优化的方法,三个指针!!
    1. 环状检测算法:当快慢指针第一次相遇的节点 meeting,到入口节点entry的距离 (沿着指针移动方向),等于, 入口节点entry 到 头节点head 的距离。所以if(slow==fast)时,开始entry和slow一起移动,直到他们相遇。
    2. 最好画图,会很清楚。

Reference

  1. Cycle detection (graph theory))
  2. Cycle detection(iterated functions)# Floyd’s cycle-finding algorithm
Thanks for Support.