LeetCode 142. 环形链表 II
题目描述
思路分析
快慢指针问题
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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 {
slow = head
for slow != fast {
slow = slow.Next
fast = fast.Next
}
return slow
}
}
return nil
}
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 // 没有环
}
- 时间复杂度：O(n)，其中
n是链表的节点数。- 空间复杂度：O(1)，只使用了常数级别的空间。
1
write your code here
本博客所有文章除特别声明外，均采用
CC BY-NC-SA 4.0
许可协议，转载请注明出处！