【面试经典150 | 链表】循环链表
Tag
【快慢指针】【哈希集合】【计数】【链表】
题目来源
题目解读
判断一个链表中是否存在环。
解题思路
链表中有环，那么在遍历链表中节点的时候就有部分元素被重复遍历，于是可以想到使用一个集合来记录已经遍历的节点，如果集合中有节点在遍历的时候第二次出现，那么一定存在环。该方法看似可以判断环的问题，但是链表中的节点会存在重复值，在无环的链表中也可能存在某些节点值被遍历了两次，导致无环链表被误判成有环链表。
如果集合中存放的是节点而不是节点的值呢？这样就可以唯一表示每一个节点了，因为每一个节点实际上是一个结构体（c语言中）或者类（c++中），都是以地址的形式存在于栈上。
接下来将介绍三种判断链表中是否有环的方法，方法一是哈希集合的方法，方法二是一种数学上的方法，方法三是一种 “巧妙” 的方法。这三种方法都推荐大家认真学习，务必要掌握。
方法一：哈希集合
遍历链表，将经过的节点存到哈希集合中，如果集合中已经存在了该节点，就说明链表中存在环。
实现代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
bool hasCycle(ListNode *head) {
unordered_set<ListNode*> st;
while (head) {
if (st.count(head)) {
return true;
}
st.insert(head);
head = head->next;
}
return false;
}
};
复杂度分析
时间复杂度：
O
(
N
)
O(N)
O(N)，其中
N
N
N 是链表中的节点数。最坏情况下我们需要遍历每个节点一次。
空间复杂度：
O
(
N
)
O(N)
O(N)，其中
N
N
N 是链表中的节点数。主要为哈希表的开销，最坏情况下我们需要将每个节点插入到哈希表中一次。
方法二：快慢指针
我们可以使用快慢指针来判断是否有环。定义一个慢指针 slow 每次只移动一个位置，定义一个快指针 fast 每次移动两个位置，两个指针从同一个节点出发：
- 如果链表中没有环，快指针一定会到达最后的
nullptr节点； - 如果链表中有环，那么两个指针一定会在环内相遇。
实现代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
bool hasCycle(ListNode *head) {
if (head == nullptr || head->next == nullptr)
return false;
ListNode *slow = head;
ListNode *fast = head->next;
while (fast != slow) {
if (fast == nullptr || fast->next == nullptr)
return false;
slow = slow->next;
fast = fast->next->next;
}
return true;
}
};
代码中的 while 循环的条件语句是 slow != fast，即快慢指针相等的时候才会退出循环。我们初始化的慢指针为 head，快指针为 head->next，如果我们将两个指针初始都置于 head，那么 while 循环就不会执行，才会对两指针进行上述的初始化，相当于快慢指针是从 dummy head（头结点的虚构的上一个）这个节点同时出发的，我们先让快慢指针出发了各自的一个步幅，这样就可以使用 while 循环了。
当然也可以使用 do...while 循环，这样的话快慢指针初始化为 head 就可以了。
while 语句与 do...while 语句的区别在于前者是先判断再执行，而后者是先执行再判断。
复杂度分析
时间复杂度：
O
(
N
)
O(N)
O(N)，其中
N
N
N 是链表中的节点数。
空间复杂度：
O
(
1
)
O(1)
O(1)。
方法三：计数
方法二就比较简单了。如果链表中存在环，那么在遍历链表的时候一定有一些节点值被重复遍历了多次。由于本题中链表最多有
1
e
4
1e4
1e4 个节点，因此我们边遍历节点边计数（从头结点到当前节点的个数），如果数量大于
1
e
4
1e4
1e4，那么链表中一定存在环，我们直接退出迭代遍历的过程，返回 false。
实现代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
bool hasCycle(ListNode *head) {
int cnt = 0;
while (head) {
++cnt;
if (cnt > (int)1e4) {
return true;
}
head = head->next;
}
return false;
}
};
复杂度分析
时间复杂度：
O
(
N
)
O(N)
O(N)，其中
N
N
N 是链表中的节点数。我们只有遍历每个节点一次之后才能判断出有没有环。
空间复杂度：
O
(
1
)
O(1)
O(1)。
拓展
本题中如果还需要求有环链表中的入环点，那么该怎么解决呢？也就是 142. 环形链表 II 这个题目要解决的问题。
最简单的方法还是哈希集合的方法，当某个节点第二次出现，该节点就是要求的入环点，该方法很简答这里不予说明。
重点来看一下如何使用 快慢指针法 来求入环点。
先来假设一些变量，入环点之前的距离为 a，入环点到快慢指针第一相遇的点的距离为 b，此时环中剩下的距离为 c，快指针在环中走了
n
n
n 圈之后，快、慢指针第一次相遇，于是快慢指针行走的位置距离为：
- 慢指针：
a+b； - 快指针：
a+b+n(b+c)。
慢指针每次走一个节点位置，快指针每次走两个节点位置，快指针走的路程就是慢指针的两倍，所以快慢指针行走的位置距离有这样的关系：
2
(
a
+
b
)
=
a
+
b
+
n
(
b
+
c
)
2(a+b)=a+b+n(b+c)
2(a+b)=a+b+n(b+c)
化简得到：
c
=
a
+
b
+
(
b
+
c
)
(
n
−
1
)
c = a+b+(b+c)(n-1)
c=a+b+(b+c)(n−1)
根据以上公式推导可以知道，当入环点到第一次相遇点的距离加上
n
−
1
n-1
n−1 圈的环的长度等于链表头部到入环点的距离。进一步来讲，如果两个指针分别从头结点和第一次相遇点出发，每次行进一个节点，那么它们相遇的节点（第一次相遇）就是入环点。
实现代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
if (head == NULL || head->next == NULL || head->next->next == NULL) {
return NULL;
}
ListNode *slow = head->next, *fast = head->next->next;
while (slow != fast) {
if (fast->next == NULL || fast->next->next == NULL) {
return NULL;
}
slow = slow->next;
fast = fast->next->next;
}
fast = head;
while (slow != fast) {
slow = slow->next;
fast = fast->next;
}
return slow;
}
};
其他语言
python3
以下是 快慢指针法 判断链表中是否有环的python3语言代码
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def hasCycle(self, head: Optional[ListNode]) -> bool:
if not head or not head.next:
return False
slow = head
fast = head.next
while fast != slow:
if not fast or not fast.next:
return False
slow = slow.next
fast = fast.next.next
return True
写在最后
如果文章内容有任何错误或者您对文章有任何疑问，欢迎私信博主或者在评论区指出 💬💬💬。
如果大家有更优的时间、空间复杂度方法，欢迎评论区交流。
最后，感谢您的阅读，如果感到有所收获的话可以给博主点一个 👍 哦。