AlgoDaily - Detect Loop in Linked List

The fastest method is to traverse the linked list using two pointers. This is a well known Computer Science technique: move one pointer by one node at a time, and the other pointer by two at a time.

If these pointers meet at the same node, then there's a loop. If the pointers don't meet, then the linked list doesn’t have a loop.

The intuition here is that the faster pointer will go through the entire list at least once, and will inevitably meet the slower node at the beginning again. If there is a loop, they'll eventually converge.

xxxxxxxxxx
    'PASSED: Assuming list1.head.next.next.next.next = list1.head, we can detect an artificial loop in the linked list'
 
var assert = require('assert');
​
function detectLoop(head) {
  // Fill in this method
  return head;
}
​
class LinkedListNode {
  constructor(val) {
    this.val = val;
    this.next = null;
  }
}
​
const list1 = new LinkedListNode(3);
const nodes = [4, 5, 6, 7, 8, 9, 10];
let head = list1;
for (let i = 0; i < nodes.length; i++) {
  const newNode = new LinkedListNode(nodes[i]);
  head.next = newNode;
  head = newNode;
}
list1.next.next.next.next.next.next = list1.next.next;
console.log(detectLoop(list1));
​
function Node(val) {
  this.val = val;

OUTPUT

Results will appear here.