LeetCode 142. 环形链表 II

题目描述

🔥 142. 环形链表 II

思路分析

  1. 快慢指针：使用两个指针 slow 和 fast，slow 每次移动一步，fast 每次移动两步。如果链表中存在环，slow 和 fast 会相遇。
  2. 找到环的入口：
    • 当 slow 和 fast 相遇后，重置 slow 指针到链表头部。
    • 然后，slow 和 fast 同时每次移动一步，直到它们再次相遇。相遇的节点就是环的入口。
  3. 时间复杂度：O (n)，其中 n 是链表的节点数。
  4. 空间复杂度：O (1)，只使用了常数级别的额外空间。

参考代码

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

// 找到环的起始节点
func detectCycle(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return nil
	}

	slow, fast := head, head

	// 找到相遇点
	for fast != nil && fast.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next

		if slow == fast { // 相遇
			entry := head
			// 找到环的起始节点
			for entry != slow {
				entry = entry.Next
				slow = slow.Next
			}
			return entry // 返回环的起始节点
		}
	}

	return nil // 没有环
}

🍏 点击查看 Java 题解

1

write your code here
本文作者:
本文链接: https://hgnulb.github.io/blog/2022/79262703
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！