AlgoDaily - Detect Loop in Linked List

Another way to think about it, notice that the distance between the two pointers increase by 1 after every iteration (one travels by 2, one travels by 1, so the distance increases). The distance is always going to be original distance + distance increase each iteration (which is 1, 2, 3, ..). Because they are moving in a fixed-length cycle, they'll eventually meet.

The space complexity of the algorithm is O(1).

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.