Leetcode 142 Linked List Cycle II

1930 ワード

Given a linked list, return the node where the cycle begins. If there is no cycle, return  null .
Follow up:Can you solve it without using extra space?
Leetcode 141 Linked List Cycleと
性質:distance from head toループ開始点==distance from二重ポインタが出会う点toループ開始点
証明:
ポインタa速度が1ポインタb速度が2
ヘッドからリングの開始までの距離をk、リングの周長をr、リングの開始から順方向から出会い点までの距離をdと記す
aから出会った地点までの道のりはSa=k+d,Sb=k+nr+d(nはb多巻きの輪数)である.
n=1をとるとSb=k+r+dは同時にSa*2=Sbを満たす
d=r−k,Sa=r,Sb=2 rは条件を満たす
n>1が成立する場合は明らかに存在しない
var detectCycle = function(head) {

    if(!head)

        return null

    var a = head

    var b = head

    while(b.next && b.next.next){

        b = b.next.next

        a = a.next

        if(a===b){

            a = head

            while(a !== b){

                a = a.next

                b = b.next

            }

            return a

        }

    } 

    return null

}