AlgoDaily - Detect Loop in Linked List

At outer loop node 1, we'd inner loop through 1.

At outer loop node 3, we'd inner loop through 1 -> 3.

At outer loop node 5, we'd inner loop through 1 -> 3 -> 5.

At outer loop node 3 again, we'd inner loop through 1 -> 3 -> 5 -> 3.

So the brute force way to do it is to conduct a nested traversal-- we can traverse all the nodes, and then at each iteration, traverse through the nodes already visited by the outer loop. In the inner loop, if we encounter a node twice, we know it's been repeated.

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.