JavaScript中的链表循环

gk7wooem  于 2023-01-04  发布在  Java
关注(0)|答案(1)|浏览(99)

我在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;
}
2ic8powd

2ic8powd1#

我会把它留在这里几行,我会把一个参考,你可以找到它的做法;希望能有所帮助:

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function (head) {
  let slow = head;
  let fast = head;
  while (fast && fast.next) {
    fast = fast.next.next;
    slow = slow.next;
    if (fast === slow) return true;
  }
  return false;
};

培训:leetcode.com
视频:https://www.youtube.com/watch?v=gBTe7lFR3vc

相关问题