Given a singly-linked-list, determine if there is a cycle.

singly-linked-list-cycle.js

/**
 * Given a singly-linked-list, determine if there is a cycle.
 */
(() => {

  // Predefine Global Structure & helper function
  class LinkedListNode {
    constructor(value) {
      this.value = value;
      this.next = null;
    }
  }
  const valuesToLinkedListNodes = (values) => {
    const nodes = [];
    for (let i = 0; i < values.length; i++) {
      const node = new LinkedListNode(values[i]);
      if (i > 0) {
        nodes[i - 1].next = node;
      }
      nodes.push(node);
    }
    return nodes;
  }
  // Node Conditional Modifier
  const modifier = (nodes) => {
    nodes[(nodes.length - 1)].next = nodes[0].next;
    return nodes;
  }

  /** --- Solutions --- **/

  // Solution 1: Use a histogram (finite set)
  // runtime complexity: o(n);
  // space cost: o(n)
  const solution1 = (nodeArray = [1, 2, 3, 4]) => {
    let nodes = valuesToLinkedListNodes(nodeArray);
    const runner = (nodes, modifier = null) => {
      if (modifier != null) {
        nodes = modifier(nodes);
      }
      let histogram = new Set();
      let activeNode = nodes[0];
      let found = false;
      while (activeNode && activeNode.next) {
        if (histogram.has(activeNode) == true) {
          activeNode = false;
          found = true;
        } else {
          histogram.add(activeNode);
          activeNode = activeNode.next;
        }
      }
      return found;
    }
    let found = runner(nodes, modifier);
    console.log(`Solution 1: Did we find it? ${found}`);
  }

  const solution2 = (nodeArray = [1, 2, 3, 4]) => {
    let nodes = valuesToLinkedListNodes(nodeArray);
    const runner = (nodes, modifier = null) => {
      if (modifier != null) {
        nodes = modifier(nodes);
      }
      const containsCycle = (firstNode) => {
        let granularPointer = firstNode;
        let specificPointer = firstNode;
        while (specificPointer && specificPointer.next) {
          granularPointer = granularPointer.next;
          specificPointer = specificPointer.next.next;
          if (specificPointer == granularPointer) {
            return true;
          }
        }
        return false;
      }
      return containsCycle(nodes[0]);
    }
    let found = runner(nodes, modifier);
    console.log(`Solution 2: Did we find it? ${found}`);
  }

  // Solution1: Use a histogram to maintain state
  // The solution is functional, but at a cost of increased space.
  // Since each element in the SinglyLinkedList has to be stored twice.
  // Space Complexity: o(n), RunTime Complexity: o(n)
  solution1();

  // Solution 2: Use two pointers to determine position.
  // The solution uses pointers (granularPointer & specificPointer)
  // to determine where they are in the relative loops. Once they equal
  // each other on next iteration, it confirms a cycle.
  // Space Complexity: o(1), Runtime Complexity: o(n)
  solution2();

})();