快慢指针是带环链表的经典解法,但同时也能用于解决如重复数字这个问题,先看环状链表求入口。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22ListNode *detectCycle(ListNode *head) {
if (!head || !head->next) return NULL;
ListNode *slow = head->next, *fast = head->next->next;
while (fast && fast->next && slow != fast) {
slow = slow->next;
fast = fast->next->next;
}
if (!fast || !fast->next) return NULL;
fast = head;
while (fast != slow) {
fast = fast->next;
slow = slow->next;
}
return slow;
}
注意几个点:
- 初始slow和fast应该是一次步骤后的位置,否则第一个循环会有问题
- 无环的条件,要及时退出。
- 注意访问变量之前检查指针是否为空!!
再看这个题:1
n+1个数,每个数属于[1,n],这个数组一定有重复,找出重复的
1 | int findDuplicate(vector<int>& nums) { |
类似上面,注意初始指针位置。这次一定有环,故不担心越界