Coding Challenge – Find out if a given singly-linked list contains a cycle.

Question: Write a function testListCycle() that takes node as argument for a given singly-linked list and returns a boolean indicating whether the list contains a cycle.

A cycle meaning when a node’s next points back to a previous node in the list which makes list non-linear and it will be loop.

To solve this problem first we need to introduce what is singly-linked list, and how to access the node and steps to check loop!

A singly linked list is collection of nodes wherein each node has 2 parts: data and a pointer to the next node. The list terminates with a node pointing at null.

Main operations on a linked list are: insert and delete.

Here is the class which creates singly linked list.

class Node{
  constructor(data, next = null){
    this.data = data,
    this.next = next
  }
}

class LinkedList{
  constructor(){
  this.head = null;
  }
}

let list = new LinkedList();

Let’s talk about the algorithm & data structure we can use to solve this problem!

We can use Set data structure to store values for each node.

Algorithm:

1. If the current node is already in our set, we have a cycle. Return true.
2. If the current node is null we’ve hit the end of the list. Return false.
3. Else throw the current node in our set and keep going.

Here is the Working Solution:

  cost testListCycle = (node) => {

    let curPointer = firstNode;
    let nextPointer = firstNode;

    while (curPointer && nextPointer.next) {
      curPointer = curPointer.next;
      nextPointer = nextPointer.next.next;

      if (nextPointer === curPointer) {
        return true;
      }
    }

    return false;
  
  }