• 0

Detect a loop in cyclic/circular linked list

Logic :

  • If a linked list has a cycle then no node has a null as next pointer.
  • A simple loop exists when p1.next.next !== null as shown below.
Simplest possible loop
Simplest possible loop
  • While iterating over the linked list we need two pointers, p1 increments one node at a time and the p2 increments two points at a time. If both the pointers meet then the loop exists.
  • If there is no loop then p1 and p2 can not meet as p2 is in the future, we have not invented time travel yet :)

    Circular Linked List iteration for the given solution
    Circular Linked List iteration for the given solution

    Watch the following video to understand the Floyd's cycle-finding algorithm!

    This post is a follow-up of JavaScript Linked List Example. I recommend reading those posts first, as the following code uses the method from it.

    Solution :


    'use strict';
    function LinkedList () {
    this.head = null;
    }
    LinkedList.prototype.hasLoop = function () {
    var p1, p2;
    p1 = this.head;
    p2 = this.head;
    // basic condition for loop to exist
    while (p2.next.next) {
    // console.log('P1 = %d, P2 = %d', p1.data, p2.data);
    p1 = p1.next;
    p2 = p2.next.next;
    if (p1 == p2) {
    return true;
    }
    }
    return false;
    };
    var L1 = new LinkedList();
    var testData = [1,2,3,4,5,6];
    testData.forEach(el => L1.insertNodeAtTail(el));
    // Create a circular linked list
    L1.head.next.next.next.next.next.next = L1.head.next.next;
    console.log(L1.hasLoop()); // true
    // Remove circular dependency
    L1.head.next.next.next.next.next.next = null;
    console.log(L1.hasLoop()); // false
    view raw detectLoop.js hosted with ❤ by GitHub

    References :