AlgoDaily - Detect Loop in Linked List

Detect Loop in Linked List (Hard)

Good evening! Here's our prompt for today.

You may see this problem at Dropbox, Databricks, Datadog, Nvidia, Visa, Tanium, Carta, Fastly, Blend, Zoominfo, Elastic, and New Relic.

What is the best way to find out if a linked list contains a loop? You're given the following data structure as the definition of a linked list node:

JAVASCRIPT

1class LinkedListNode {
2	constructor(val) {
3		this.val = val;
4		this.next = null;
5	}
6}

A loop or a cycle in graph theory is a path of nodes and edges where a node is reachable from itself.

Implement a detectLoop method that takes a linked list head node as the parameter and returns true or false depending on whether there's a cycle.

Constraints

Length of the linked list <= 10000
Value stored in each node will be between -1000000000 and 1000000000
Expected time complexity : O(n)
Expected space complexity : O(1)

xxxxxxxxxx
​
 
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.