文章目錄
- 環鏈
- 環形鏈表
- 題目
- 分析
- 延伸問題：
- ==1.為什么fast和slow會在環中相遇，會不會有這么一種情況呢，就是在環中一直交錯永遠遇不上？請證明一下，==
- 證明：
- ==這里就又衍生出了一個問題就是slow與fast只要是步差為一就可以相遇==
- ==2.為什么slow走一步，fast走兩步呢？fast可不可以走大于兩步呢？==
- [環形鏈表 II](https://leetcode-cn.com/problems/linked-list-cycle-ii/)
- 題目
- 分析
環鏈
環形鏈表
題目
分析
我們剖析一下代碼
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;
}
延伸問題：
1.為什么fast和slow會在環中相遇，會不會有這么一種情況呢，就是在環中一直交錯永遠遇不上？請證明一下，
結論：就上面fast和slow而言是一定相遇的
證明：
第一步：slow和fast，fast肯定是先進環，這時slow是fast入環前距離的一半，
第二步：隨著slow進環，fast已經在環里走了一段了，走了 多少和環的大小有關系
第三步：我們這里假設slow進環的時候距離和fast是N
slow每次往前走1步，fast往前走兩步，每追一次，判斷一下相遇，結果為N-1，也就是說每追一次他們間的距離是一步一步的在減少，直到他們相遇
這里就又衍生出了一個問題就是slow與fast只要是步差為一就可以相遇
2.為什么slow走一步，fast走兩步呢？fast可不可以走大于兩步呢？
結論：fast走n步，n>2,不一定會相遇
這里分析一個slow走一步，fast走三步的交錯與不交錯的情況
他們之間的距離變化是每次是兩兩的減少，這也就意味著可能會交錯
上面的奇偶問題也就又衍生出了N是他們的步差倍數就能相遇
環形鏈表 II
題目
如何求環的入口點
分析
我們先直接放結論一個指標從相遇點開始走，一個指標從鏈表頭開始走，他們會在環的入口點相遇
struct ListNode *detectCycle(struct ListNode *head) {
struct ListNode * fast = head,* slow = head;
while(fast && fast->next)
{
fast = fast->next->next;
slow = slow->next;
if(slow == fast)//相遇
{
//相遇節點
struct ListNode * meetNode = fast;
while(meetNode != head)
{
meetNode = meetNode->next;
head = head->next;
}
return meetNode;
}
}
return NULL;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/339154.html
標籤：其他
上一篇：網路基本概念總結