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

wendux 發(fā)布于2019-08-22 18:06 / 2958人閱讀

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

題目描述

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

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

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

判斷鏈表有環(huán)

通常判斷鏈表是否有環(huán)，會采用快慢指針的方法，其實道理很簡單，就像兩個人賽跑且一個人跑得快一個人跑得慢。如果賽道是直的，那么快人跑到終點時慢人還未到；如果賽道是環(huán)形，則快人和慢人總會相遇。
代碼實現(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;
    // 快慢指針相遇時，跳出while循環(huán)
    if(slow === fast)
        break;
}
// 快指針已經(jīng)到了鏈表尾部了還沒和慢指針相遇，說明沒有環(huán)
if(fast === null || fast.next === null)
    return null;
    
// 后續(xù)會處理有環(huán)的情況...
}

找到入環(huán)節(jié)點

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

如圖，設(shè)整個鏈表長度為L，環(huán)長度為R，且距離具有方向性，例如CB是C點到B點的距離，BC是B點到C點的距離，CB!=BC。當(dāng)證明有環(huán)時，fast和slow都順時針到了B點，則此時：
slow走的距離：AC+CB
fast走的距離：AC+k*R+CB(k=0,1,2...)
由于fast每次走2個節(jié)點，slow每次走1個節(jié)點，所以：
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點出發(fā)以速度1前進、快指針從B點出發(fā)以速度1前進，則慢指針到C點時，快指針也必然到了。
代碼實現(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重新相遇時，相遇節(jié)點就是入環(huán)節(jié)點
    while(slow !== fast) {
        slow = slow.next;
        fast = fast.next;
    }

    return slow;
}