【刷算法】判斷鏈表是否有環以及返回入環節點

wendux 發布于2019-08-22 18:06 / 2950人閱讀

摘要：為什么這么做就可以保證在入環節點相遇證明一下如圖，設整個鏈表長度為，環長度為，且距離具有方向性，例如是點到點的距離，是點到點的距離，。代碼實現有環，重新回到鏈表頭和重新相遇時，相遇節點就是入環節點

題目描述

判斷一個單鏈表是否有環，有環則返回入環節點，否則返回null

1->2->3->4->5->6
            ↑  ↓
            8<-7

例如上面這個鏈表就有環，入環節點是5

判斷鏈表有環

通常判斷鏈表是否有環，會采用快慢指針的方法，其實道理很簡單，就像兩個人賽跑且一個人跑得快一個人跑得慢。如果賽道是直的，那么快人跑到終點時慢人還未到；如果賽道是環形，則快人和慢人總會相遇。
代碼實現

function ListNode(x){
    this.val = x;
    this.next = null;
}
function EntryNodeOfLoop(pHead){
if(pHead === null)
    return null;
// 快慢指針從鏈表的頭部開始
var fast = pHead;
var slow = pHead;

while(fast.next !==null && fast.next.next !== null) {
// 快指針每次走兩步；慢指針每次走一步
    slow = slow.next;
    fast = fast.next.next;
    // 快慢指針相遇時，跳出while循環
    if(slow === fast)
        break;
}
// 快指針已經到了鏈表尾部了還沒和慢指針相遇，說明沒有環
if(fast === null || fast.next === null)
    return null;
    
// 后續會處理有環的情況...
}

找到入環節點

常見的方法是：在確定鏈表有環之后，慢指針重新指向鏈表頭，快指針留在相遇處；然后快慢指針再以每次移動1個節點的速度前進，最終他們在入環節點相遇。
為什么這么做就可以保證在入環節點相遇？證明一下：

如圖，設整個鏈表長度為L，環長度為R，且距離具有方向性，例如CB是C點到B點的距離，BC是B點到C點的距離，CB!=BC。當證明有環時，fast和slow都順時針到了B點，則此時：
slow走的距離：AC+CB
fast走的距離：AC+k*R+CB(k=0,1,2...)
由于fast每次走2個節點，slow每次走1個節點，所以：
2(AC+CB) = AC+k*R+CB
AC+CB = k*R
AC+CB = (k-1)*R+R
AC = (k-1)*R+R-CB
AC = (k-1)*R+BC
從最終的表達式可以看出來，AC的距離等于繞環若干圈后再加上BC的距離，也就是說慢指針從A點出發以速度1前進、快指針從B點出發以速度1前進，則慢指針到C點時，快指針也必然到了。
代碼實現：

function ListNode(x){
    this.val = x;
    this.next = null;
}
function EntryNodeOfLoop(pHead){
    if(pHead === null)
        return null;
    var fast = pHead;
    var slow = pHead;

    while(fast.next !==null && fast.next.next !== null) {
        slow = slow.next;
        fast = fast.next.next;
        if(slow === fast)
            break;
    }

    if(fast === null || fast.next === null)
        return null;
    // 有環，slow重新回到鏈表頭
    slow = pHead;
    
    // slow和fast重新相遇時，相遇節點就是入環節點
    while(slow !== fast) {
        slow = slow.next;
        fast = fast.next;
    }

    return slow;
}

云服務器 GPU云服務器鏈表算法鏈表排序算法算法 c語言鏈表判斷是否

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/95503.html

大廠算法面試之leetcode精講7.雙指針

摘要：空間復雜度雙指針，循環數組，較小的那個先向內移動如果高的指針先移動，那肯定不如當前的面積大計算面積更新最大面積相交鏈表方法哈希表思路將鏈表存入中，第一個相同的節點就是重合的節點復雜度時間復雜度，分別是兩個鏈表的長度。大廠算法面試之leetcode精講7.雙指針視頻教程（高效學習）:點擊學習目錄：1.開篇介紹2...

不知名網友 2021-11-26 11:11 評論0 收藏0
Leetcode：刷完31道鏈表題的一點總結

摘要：既然說到地址空間了就順帶說一下上面環形鏈表這道題的另一種很的解法吧。介紹完常規操作鏈表的一些基本知識點后，現在回到快慢指針。 ??前幾天第一次在 Segmentfault 發文—JavaScript：十大排序的算法思路和代碼實現，發現大家似乎挺喜歡算法的，所以今天再分享一篇前兩個星期寫的 Leetcode 刷題總結，希望對大家能有所幫助。 ??本文首發于我的blog 前言 ??今天終于...

DevTalking 2019-08-23 17:50 評論0 收藏0
JAVASCRIPT算法（6）

摘要：還是鏈表算法題目描述給出兩個無環單鏈表判斷和是否相交。所以可以得出另外一種解法，先遍歷鏈表，記住尾節點，然后遍歷鏈表，比較兩個鏈表的尾節點，如果相同則相交，不同則不相交。想法還是奇妙的。算法寫起來不難，難的是想到這個。還是鏈表算法題目描述：給出兩個無環單鏈表A: a1 → a2 ↘ c1 → c2 → c3 → ...

FreeZinG 2019-08-21 17:56 評論0 收藏0
寫一段代碼判斷單向鏈表中有沒有形成環，如果形成環，請找出環的入口處，即P點

摘要：由于要比移動的快，如果有環，一定會先進入環，而后進入環。現在問題就簡單了，由于移動的距離永遠是的一般，因此當遍歷玩整個環長度個節點的時候正好遍歷了個節點，也就是說，此時正好指向距離最遠的點。首先，關于單鏈表中的環，一般涉及到以下問題： 1.給一個單鏈表，判斷其中是否有環的存在； 2.如果存在環，找出環的入口點； 3.如果存在環，求出環上節點的個數； 4.如果存在環，求出鏈表的長度； ...

OldPanda 2019-07-01 13:56 評論0 收藏0