环形链表问题（详细证明过程）

2024-07-15 21:41| 来源: 网络整理| 查看: 265

判断链表是否有环（龟兔赛跑）

题目描述：给定一个链表，判断链表中是否有环。在这里插入图片描述思路：可以明确的是：若一个链表带环，那么用指针一直顺着链表遍历，最终会回到某个地方。我们可以定义两个指针（快慢指针），两个指针均从表头开始同时遍历链表，快指针一次走两步，慢指针一次走一步。如果链表带环，那么快慢指针一定会相遇，否则快指针会先遍历完链表（遇到NULL）。若是你不明白为什么链表带环，快慢指针就一定会相遇，那么你可以想想龟兔赛跑：在这里插入图片描述代码：

struct ListNode { int val; struct ListNode *next; }; bool hasCycle(struct ListNode *head) { struct ListNode* slow = head; struct ListNode* fast = head; while (fast && fast->next) { fast = fast->next->next;//兔子走两步 slow = slow->next;//乌龟走一步 if (fast == slow)//兔子与乌龟相遇 return true; } return false; } 返回链表开始入环的第一个结点

题目描述：给定一个链表，返回链表开始入环的第一个结点。如果链表无环，则返回NULL。

这不是一道简简单单的代码题，严格来说，这是一道数学推论题，若是不能得出最终推论，是不能很好的解决该问题的。

推论如下：在这里插入图片描述根据最终推论可以得出结论：若一个指针从出发点开始走，另一个指针从相遇点开始走，则他们最终会在入口点处相遇。代码：

struct ListNode { int val; struct ListNode *next; }; struct ListNode *detectCycle(struct ListNode *head) { struct ListNode* fast = head; struct ListNode* slow = head; while (fast && fast->next) { slow = slow->next;//慢指针走一步 fast = fast->next->next;//快指针走两步 if (fast == slow)//相遇 { struct ListNode* meet = fast;//相遇点 while (head != meet) { head = head->next;//一个指针从出发点开始走 meet = meet->next;//一个指针从相遇点开始走 } return meet;//两个指针相遇，返回当前结点 } } return NULL;//链表不带环 } 面试还可能出现的问题

问题一：为什么慢指针走一步，快指针走两步，他们一定会在环里面相遇？会不会永远追不上？请证明。

不会永远追不上，证明如下：在这里插入图片描述问题二：那么慢指针走一步，快指针走三步？走四步？或是走n步行不行？为什么？请证明。

不行，这样可能会追不上，证明如下：在这里插入图片描述总结一下：当慢指针走一步，快指针走三步时。若慢指针进环时与快指针之间的距离为奇数，并且环的周长恰好为偶数，那么他们会一直在环里面打转转，永远不会相遇。（当慢指针走一步，快指针走四步或是走n步时，证明过程类似）

【本文地址】

环形链表问题（详细证明过程）

环形链表问题（详细证明过程）

今日新闻

推荐新闻