废话不多说直接上题
题目链接:141. 环形链表
题目示例
[思路]:快慢指针遍历链表,(快指针每次走两步,慢指针每次一步),如果链表中存在环那么快慢指针一定会相遇,否则快指针会先到达链尾。
就好比带环就是在操场绕圈跑步,不管什么时候开始、如果一直跑,跑的快的一定会追上跑的慢的人
【问题】那为什么快指针每次走两步,三步可以吗?四步…
• 为什么快指针走两步,慢指针走一步可以?
假设链表带环,两个指针都会先后进入环内,快指针先,慢指针后进。
因此:在慢指针走完一圈之前,快指针肯定是可以追上慢指针的,即相遇。不会存在套圈的情况
• 快指针一次走3步,走4步,…n步行吗?
答案是不行!
如果快指针每次走3步,慢指针走一步,假设进环时两指针位置如图所示:
可以发现上图中快指针每次都将慢指针跳过套圈,所以循环无法满足条件退出(4步情况同理);所以只有快指针每次走一步才满足所有情况
第一个题,链表判环代码如下
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
/* 两个指针从链表其实位置开始运行,如果链表带环则一定会在环中相遇,否则快指针率先走到链表的末尾 */
bool hasCycle(ListNode *head) {
ListNode* fast = head, *slow = head;
while(fast != nullptr && fast->next != nullptr){
fast = fast->next->next;
slow = slow->next;
// 每移动一次检测是否在同一位置
if(fast == slow)
return true;
}
return false;
}
};
题目链接:142. 环形链表 II
此时已经可以判断链表是否有环了,那么接下来要找这个环的入口了。
先给出结论 方便做题使用
一个指针从起始位置开始,另一个从快慢指针相遇位置开始,每次都移动一个节点,最后相遇点就是环的入口。
所以不管快指针走了n圈,反正都是相遇点为M,环入口点为E都是固定的,
所以从快指针到入口点距离和起点到入口距离一定相等
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
// 判断是否存在环,存在返回快慢指针相遇节点;不存在返回nullptr
ListNode* hasCycle(ListNode *head) {
ListNode* fast = head, *slow = head;
while(fast != nullptr && fast->next != nullptr){
fast = fast->next->next;
slow = slow->next;
if(fast == slow)
return fast;
}
return nullptr;
}
ListNode *detectCycle(ListNode *head) {
ListNode* cur = hasCycle(head);
if(cur == nullptr) return nullptr;
ListNode* cur1 = head;
while(cur1 != cur){
cur1 = cur1->next;
cur = cur->next;
}
// 相遇节点为环入口
return cur;
}
};
上述代码存在冗余,优化后如下
ListNode *detectCycle(ListNode *head) {
ListNode* fast = head, *slow = head;
ListNode* cur = head;
while(fast != nullptr && fast->next != nullptr){
fast = fast->next->next;
slow = slow->next;
// 快慢指针相遇,此时从head 和 相遇点,同时查找直至相遇
if(fast == slow){
while(fast != cur){
fast = fast->next;
cur = cur->next;
}
// 相遇节点为环入口
return cur;
}
}
return nullptr;
}