【LeetCode】LeetCode刷题(3)【链表】【环形链表】&扩展(C语言)
我的小站——半生瓜のblog
环形链表
141. 环形链表 - 力扣(LeetCode) (leetcode-cn.com)
什么是链表带环:链表的最后一个元素不指向空而指向前面的某个结点。
思路:快慢指针,慢指针走一步,快指针走两步,二者先后 进入环内进行追逐,最终会在某个点相遇。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
bool hasCycle(struct ListNode *head) {
struct ListNode* slow = head;
struct ListNode* fast = head;
while(fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
if(slow == fast)
return true;
}
return false;
}
扩展:
请证明:
(1)slow和fast一定会在环里面相遇呢?有没有可能永远追不上? 答: 当slow 走1步,fast走2步时,一定可以追上。 若slow和fast已经进入环中,追逐已经开始了,假设他们之间的距离是N,slow走1步,fast走2步,二者的距离每次缩减1,N,N-1,N-2,......0,直到相遇。
(2)slow一次走1步,fast一次走3不行不行?4不行不行?
答:
不一定可以追上,甚至有可能会进入死循环。我比你快不一定追上,因为存在错过。若开始追逐,假设二者距离为N,假设slow走1步,fast走3步,距离每次缩减2,N,N-2,N-4,N-6......。如果N是偶数最后会减到0,如果N是偶数则减到-1,距离为0代表相遇,距离为-1代表反超了,进入新的追逐,他们之间的距离是 C-1(假设C 是环的长度),如果C-1是偶数,就可以追上,如果C-1是奇数,就永远追不上,因为是奇数的时候又像开始那样反超,距离又是C-1,就永远追不上。
其他fast步数同理分析。