我在JavaScript中遇到了下面的代码,用于检测LinkedList循环,但我不清楚为什么需要“pause”变量?还有,为什么fast
需要以两倍的速度递增,而不是只提前一个?
var fast = linkedList;
var slow = linkedList;
var pause = true;
while (fast = fast.next) {
if (fast === slow) {
return true;
}
if (!pause) {
slow = slow.next;
}
pause = !pause
}
return false;
走查,假设while条件为真,最多6次迭代:
//first iteration ----> pause is true
//fast = linkedList.next
//slow = linkedList
//pause is now false.
//second iteration ----> pause is now false!
//fast = linkedList.next.next
//slow = linkedList.next
//pause is now true
//third iteration ---> pause is now true.
//fast = linkedList.next.next.next
//slow = linkedList.next
//pause is now false
//fourth iteration ----> pause is now false!
//fast = linkedList.next.next.next.next
//slow = linkedList.next.next
//pause is now true
//fifth iteration ---> pause is true
//fast = linkedList.next.next.next.next.next
//slow = linkedList.next.next
//sixth iteration ---> pause is false
//fast = linkedList.next.next.next.next.next.next
//slow = linkedList.next.next.next
下面是我最初对这个问题的尝试,我很好奇我最初的方法有什么问题?
var slower = linkedList.value; // this is the head value
var faster = linkedList.next; //start faster one ahead
//if there is no next value or faster itself does not have a next value
if (!faster || !faster.next || !slower.next) {
return false;
}
//if faster ever equals slower, then there are duplicates!
if (faster === slower || faster.next === slower || faster === faster.next ||
slower === slower.next) {
return true;
}
// keep advancing the pointers!
else {
faster = faster.next.next;
slower = slower.next;
}
1条答案
按热度按时间2ic8powd1#
我会把它留在这里几行,我会把一个参考,你可以找到它的做法;希望能有所帮助:
培训:leetcode.com
视频:https://www.youtube.com/watch?v=gBTe7lFR3vc