Leetcode 142 Linked List Cycle II
1930 ワード
Given a linked list, return the node where the cycle begins. If there is no cycle, return
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が成立する場合は明らかに存在しない
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
}