今天接着链表的经典问题环形问题。大家一定要自己动手多写写。🙂
- 快慢指针（保持相对距离/保持相对速度）
- 野指针
- 考虑为NULL的情况
- 带环链表：尾节点的next指向链表中的任意点（甚至可能指向它自己）
- 循环条件
- 结论
环形问题的思考
假设现有一个链表是带环的，请你做出如下思考和证明！ （环形链表如下）
❓Q1
slow一次走1步，fast一次走2步，他们一定会相遇吗？（slow在走满一圈之前)
假设链表带环，两个指针最后都会进入环，快指针先进环，慢指针后进环。当慢指针刚进环时，可能就和快指针相遇了，最差情况下两个指针之间的距离刚好就是环的长度。此时，两个指针每移动一次，之间距离缩小一步，不会出现每次刚好是套圈的情况。
- 因此：在满指针走到一圈之前，快指针肯定是可以追上慢指针的，即相遇
❓Q2
slow一次走1步，fast一次走3步，他们一定会相遇吗？
- 如果N是偶数第一圈就直接追上了。
- 如果N是奇数，C是奇数，C-1是偶数，第二圈也追上了。
- 如果N是奇数，C是偶数，C-1是奇数，永远追不上。
- N是slow开始入环，fast的最初开始追击的距离。
- C是环的长度。
🙂Q2
在上面的基础上，请问N是奇数，C是偶数，C-1是奇数这个条件是否成立。请证明！
- 起点到入环的距离：L
- N是slow开始入环，fast的最初开始追击的距离。
- 环的长度：C
- slow每次走1步
- fast每次走3步
- 关键点：从开始位置到slow入环的路程，速度是3倍关系，同一时间段，路程是3倍的关系。
- 结论：N是奇数，C是偶数，C-1是奇数这个条件不成立。
❓Q3
slow一次走n步，fast一次走m步，他们一定会相遇吗？(m>n>1)
- 如果 N%(m-n) == 0 第一圈就直接追上了。
- 如果 N%(m-n) == x 第一圈也追不上了。
- 如果 (C-x)%(m-n) == 0 第二圈就追上了。
- 如果 (C-x)%(m-n) ！= 0 永远追不上了。
- N是slow开始入环，fast的最初开始追击的距离。
- C是环的长度。
❓Q4
请证明：
让一个指针slow从链表起始位置开始遍历链表，同时让一个指针fast从判环时相遇点的位置开始绕环运行，注意slow每次走1步，fast每次走1步，最终肯定会在入口点的位置相遇。
- 起点到入环的距离：L
- 入口点到相遇点：X
- 环的长度：C
- slow每次走1步
- fast每次走2步
- 关键点：从起始点到相遇点路程。速度是二倍关系。同一时间段，路程也是2倍的关系。
- 结论：一个指针从相遇点开始走，一个指正从头开始走，他们会在入口点相遇
8.环形链表
给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false 。
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。
【快慢双指针】
思路：快慢指针，即慢指针一次走一步，快指针一次走两步，两个指针从链表其实位置开始运行，
如果链表带环则一定会在环中相遇，否则快指针率先走到链表的末尾。
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ bool hasCycle(struct ListNode *head) { struct ListNode *faster=head; struct ListNode *slow=head; //一起走faster走2步 slow走1步--保持相对速度 while(faster && slow && faster->next) { faster=faster->next->next; slow=slow->next; if(slow == faster) { return true; } } return false; }
//另外写法
bool hasCycle(struct ListNode *head) { struct ListNode *faster=head; struct ListNode *slow=NULL; if(head == NULL) { return false; } while(faster != slow) { if(slow == NULL) { slow=head; } if(faster == NULL || faster->next == NULL) { return false; } faster=faster->next->next; slow=slow->next; } return true; }
9.环形链表Ⅱ
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。
输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。
【快慢指针】
- 找到相遇的地方
- 让一个指针slow从链表起始位置开始遍历链表，同时让一个指针fast从判环时相遇点的位置开始绕环运行，注意slow每次走1步，fast每次也走1步，最终会在入口点的位置相遇。（结论）
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode *detectCycle(struct ListNode *head) { struct ListNode *slow=head; struct ListNode *fast=head; struct ListNode *meet=NULL; while(fast && fast->next) { fast=fast->next->next; slow=slow->next; if(fast == slow) { slow=head; while(fast != slow) { slow=slow->next; fast=fast->next; } return fast; } } return NULL; }
【链表的相交】
感谢各位！下篇我们开始双向链表的学习。一起加油💪小伙伴们！
【链表练习题】链表知识点题库 - 力扣（LeetCode）
牛客网在线编程_算法篇_面试必刷TOP101 (nowcoder.com)
代码---------→【唐棣棣 (TSQXG) - Gitee.com】
联系---------→【邮箱：2784139418@qq.com】
