Good afternoon! Here's our prompt for today.

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:

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)

Try to solve this here or in Interactive Mode.

How do I practice this challenge?

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;

  this.next = null;

}

Here's our guided, illustrated walk-through.

How do I use this guide?