1. 环形链表
题目描述
解题思路
在这道题中, 判断链表是否存在环, 可以转换为快慢指针追击问题
快指针一次走两步, 慢指针一次走一步，当慢指针进环, 快指针追击慢指针
如果快指针追到了慢指针，就可以证明该链表带环
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
bool hasCycle(struct ListNode *head) {
struct ListNode *fast = head, *slow = head;
while (fast && fast->next)
{
fast = fast->next->next;
slow = slow->next;
if (fast == slow)
{
return true;
}
}
return false;
}证明
这里追击问题存在一定的逻辑缺陷需要证明, 比如
快指针一次走两步, 慢指针一次走一步， 快指针一定可以追到慢指针? 有没有可能错过? 有没有可能追不到 ?
快指针一次走三步, 慢指针一次走一步， 快指针一定可以追到慢指针? 有没有可能错过? 有没有可能追不到 ?
如果fast快指针一次走两步, slow慢指针一次走一步, 是一定可以追到
设fast到slow之间的距离为N，fast一次走两步, slow一次走一步, 每走一次, fast跟slow之间的距离-1 ( N-1 -> N-2 ..... 1 -> 0), 当N为0时, 则为追上, 所以一定可以追上
如果fast一次走三步, slow一次走一步，则不一定可以追上, 需要分情况考虑
如果N为偶数, 每走一次, fast跟slow之间的距离-2 ( N-2 -> N-4 ..... 2 -> 0), 可以追上
如果N为奇数, 之间的距离 ( N-2 -> N-4 .....3 -> 1 -> -1), 则会错过。这里-1表示fast跟slow之间的距离 C (周长) - 1, 相当于开始新一轮的追击, 如果C - 1为偶数, 新一轮就可以追上, 如果为C-1为奇数, 则永远追不上(进入死循环), 快指针追不到慢指针
2. 环形链表进阶
题目描述
解题思路
首先, 用快慢指针判断是否是环形链表，然后, 找入环的第一个节点
如果要找入环的第一个节点, 首先必须证明一个结论：一个指针从相遇点开始走, 一个指针从起始点开始走，最终会在入口点(入环的第一个节点）相遇
设起始点到入口点的距离为 L， 入口点到相遇点的距离为X (0 <= X < C )，环的周长为C
(0 <= X), 因为slow跟fast有可能在入口点(入环的第一个节点) 相遇
(X < C), 因为slow绝对不可能走完一个环的周长, 如果slow走完了一圈, fast肯定已经走完了两圈, fast不可能走了两圈都追不到slow, 所以X < C
然后, 就可以推断出slow走的距离为 L + X, fast走的距离为 L + N*C + X, N等于fast在环里转的圈数
因为fast的步长是slow的两倍, 所以成等式 ——> 2(L+X）= L+N*C+X ——>化简 ——> L = N*C - X
最后根据这个等式L = N*C - X ，可以证明, 一个指针从相遇点开始走, 一个指针从起始点开始走，最终会在入口点(入环的第一个节点）相遇
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode *detectCycle(struct ListNode *head) {
struct ListNode* slow = head, *fast = head;
// 判断带环
while (fast && fast->next)
{
fast = fast->next->next;
slow = slow->next;
if (fast == slow)
{
struct ListNode* meet = slow;
struct ListNode* start = head;
// 找入环第一个节点
while (meet != start)
{
meet = meet->next;
start = start->next;
}
return meet;
}
}
return NULL;
}