142. 环形链表 II
题目描述
给定一个链表的头节点 head
,返回链表开始入环的第一个节点。 如果链表无环,则返回 null
。
如果链表中有某个节点,可以通过连续跟踪 next
指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos
来表示链表尾连接到链表中的位置(索引从 0
开始)。如果 pos
是 -1,则在该链表中没有环。注意:pos
不作为参数进行传递,仅仅是为了标识链表的实际情况。
不允许修改 链表。
出处:LeetCode
解法一:哈希表
思路
我们可以使用哈希表来判断链表中是否有环。我们定义一个哈希表 set
,然后遍历链表,每次遍历时,我们判断当前节点是否在哈希表中,如果在,则说明链表中有环,返回当前节点;否则,我们将当前节点加入哈希表中。当遍历结束后,说明链表中没有环,返回 null
。
实现
function detectCycle(head: ListNode | null): ListNode | null {
const set = new Set<ListNode>();
while (head !== null) {
if (set.has(head)) {
return head;
}
set.add(head);
head = head.next;
}
return null;
}
复杂度分析
- 时间复杂度:
- 空间复杂度:
解法二:快慢指针
思路
我们可以使用快慢指针来判断链表中是否有环。我们定义两个指针 slow
和 fast
,分别指向链表的头节点 head
。然后我们遍历链表,每次迭代时,slow
指针向后移动一个节点,fast
指针向后移动两个节点。如果链表中有环,那么 slow
和 fast
指针一定会在环中相遇。当 slow
和 fast
指针相遇时,我们将 fast
指针重新指向链表的头节点 head
,然后 slow
和 fast
指针同时向后移动一个节点,直到 slow
和 fast
指针再次相遇。此时,slow
和 fast
指针相遇的节点就是链表开始入环的第一个节点。
实现
function detectCycle(head: ListNode | null): ListNode | null {
let slow: ListNode | null = head;
let fast: ListNode | null = head;
while (fast !== null && fast.next !== null) {
slow = slow!.next;
fast = fast.next.next;
if (slow === fast) {
fast = head;
while (slow !== fast) {
slow = slow!.next;
fast = fast!.next;
}
return slow;
}
}
return null;
}
复杂度分析
- 时间复杂度:
- 空间复杂度: