亚洲中字慕日产2020,大陆极品少妇内射AAAAAA,无码av大香线蕉伊人久久,久久精品国产亚洲av麻豆网站

資訊專欄INFORMATION COLUMN

【刷算法】判斷鏈表是否有環(huán)以及返回入環(huán)節(jié)點(diǎn)

wendux / 3021人閱讀

摘要：為什么這么做就可以保證在入環(huán)節(jié)點(diǎn)相遇證明一下如圖，設(shè)整個(gè)鏈表長度為，環(huán)長度為，且距離具有方向性，例如是點(diǎn)到點(diǎn)的距離，是點(diǎn)到點(diǎn)的距離，。代碼實(shí)現(xiàn)有環(huán)，重新回到鏈表頭和重新相遇時(shí)，相遇節(jié)點(diǎn)就是入環(huán)節(jié)點(diǎn)

題目描述

判斷一個(gè)單鏈表是否有環(huán)，有環(huán)則返回入環(huán)節(jié)點(diǎn)，否則返回null

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

例如上面這個(gè)鏈表就有環(huán)，入環(huán)節(jié)點(diǎn)是5

判斷鏈表有環(huán)

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

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;
    // 快慢指針相遇時(shí)，跳出while循環(huán)
    if(slow === fast)
        break;
}
// 快指針已經(jīng)到了鏈表尾部了還沒和慢指針相遇，說明沒有環(huán)
if(fast === null || fast.next === null)
    return null;
    
// 后續(xù)會(huì)處理有環(huán)的情況...
}
找到入環(huán)節(jié)點(diǎn)

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

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

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;
    // 有環(huán)，slow重新回到鏈表頭
    slow = pHead;
    
    // slow和fast重新相遇時(shí)，相遇節(jié)點(diǎn)就是入環(huán)節(jié)點(diǎn)
    while(slow !== fast) {
        slow = slow.next;
        fast = fast.next;
    }

    return slow;
}

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://www.ezyhdfw.cn/yun/95503.html

相關(guān)文章

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

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

    不知名網(wǎng)友 評論0 收藏0

  • Leetcode：刷完31道鏈表題的一點(diǎn)總結(jié)

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

    DevTalking 評論0 收藏0

  • JAVASCRIPT算法（6）

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

    FreeZinG 評論0 收藏0

  • 寫一段代碼判斷單向鏈表中有沒有形成環(huán)，如果形成環(huán)，請找出環(huán)的入口處，即P點(diǎn)

    摘要：由于要比移動(dòng)的快，如果有環(huán)，一定會(huì)先進(jìn)入環(huán)，而后進(jìn)入環(huán)?，F(xiàn)在問題就簡單了，由于移動(dòng)的距離永遠(yuǎn)是的一般，因此當(dāng)遍歷玩整個(gè)環(huán)長度個(gè)節(jié)點(diǎn)的時(shí)候正好遍歷了個(gè)節(jié)點(diǎn)，也就是說，此時(shí)正好指向距離最遠(yuǎn)的點(diǎn)。 首先，關(guān)于單鏈表中的環(huán)，一般涉及到以下問題： 1.給一個(gè)單鏈表，判斷其中是否有環(huán)的存在； 2.如果存在環(huán)，找出環(huán)的入口點(diǎn)； 3.如果存在環(huán)，求出環(huán)上節(jié)點(diǎn)的個(gè)數(shù)； 4.如果存在環(huán)，求出鏈表的長度； ...

    OldPanda 評論0 收藏0

發(fā)表評論

0條評論

最新活動(dòng)
閱讀需要支付1元查看
<