Javascript: Detect and Remove a loop from cylic linked list

Question

I have used Javascript to write a circular linked list and to detect and remove the loop.It is working fine untill the part of loop detection. How ever it is failing to remove the loopnode. More specifically: the removeLoop function of this code doesnot work.

Here is my code:

    function Node(element){
        this.element = element;
        this.next = null;
    }

    //circular linked list class

    function LList() {
        this.head = new Node("head");
        this.head.next = this.head;
        this.find = find;
        this.insert = insert;
        this.display = display;


    }

    function find(item){
        var curr = this.head;
        while(curr.element != item){
            curr = curr.next;
        }
        return curr;
    }

//inserting items into linked list

    function insert(newElem, after){
        var newNode = new Node(newElem);
        var curr = this.find(after);
        newNode.next = curr.next;
        curr.next = newNode;
    }

    function display() {
        var currNode = this.head;
        while ((currNode.next !== null) &&
        (currNode.next.element !== "head")) {
            console.log(currNode.next.element);
            currNode = currNode.next;
        }
    }

    function findPrevious(item){
     var curr = this.head;
        while(curr.next !== null && curr.next.element !== item){
            curr =curr.next;
        }
        return curr;
    }

    //creating a linkedlist object

    var furniture = new LList();
    furniture.insert("chair","head");
    furniture.insert("table", "chair");
    furniture.insert("couch", "table");
    furniture.insert("stool","couch");
    //furniture.display();

    //detecting if a linked list is circular

    function detectALoop(list){
        var slow = list.head;
        var fast = list.head;
        while(slow && fast && fast.next){
            slow = slow.next;
            fast = fast.next.next;

            if(slow === fast){
               removeLoop (slow, list);
                return 1;
            }
        }
        return 0;
    }

    //This part of the code doesnot work

    function removeLoop(loopNode, list)
    {
        var ptr1 = loopNode;
        var ptr2 = loopNode;
        var looplen = 1,i;


        // count the number of nodes in loop

        while(ptr1.next != ptr2)
        {
            ptr1 = ptr1.next;
            looplen++;
        }
        console.log(looplen)
        ptr1 = list.head;
        ptr2 = list.head;
        for(i=0; i <= looplen; i++)
        {
            ptr2 = ptr2.next;
        }



        while(ptr2.next != ptr1.next)
        {
            ptr1 = ptr1.next;
            ptr2 = ptr2.next;
        }

        ptr2.next = null; // breaking the loop
    }


    console.log(detectALoop(furniture))
    furniture.display();

Answer 1

You are making this a lot more complicated than it needs to be if the loop has to be back onto the first element.

function breakLoop(list) {
    var head = list.head, tail = head, len = 1;
    while (tail.next != head) {
        len++;
        tail = tail.next;
    }
    tail.next = null;
    console.log(len.toString());
}

Now if you may need to handle any arbitrary loop, I still have no idea what you need 3 loops for. Use an ES6 Set; most browsers now support this, I believe. I'm going to go ahead and return the length instead of logging it.

function breakLoopAnywhere(list) {
    var seen = new Set, node = list.head;
    while (!seen.has(node.next)) {
        seen.add(node);
        node = node.next;
    }
    node.next = null;
    return seen.size;
}

If you don't have sets, you can hack it with an array, replacing has with indexOf and add with push.

If you feel you must have the ability to detect a loop vs a non-looping list without breaking it:

// takes a node, returns the node 
// that points backwards on its next
function getLoopNode(node) {
    var seen = new Set; 
    do {
        seen.add(node);
    } while (!seen.has(node.next) && node = node.next)
    return node;
}

function detectLoop(node) {
    return getLoopNode(node) != null;
}

function breakLoop(node) {
    node = getLoopNode(node);
    if (node) node.next = null;
}

Your detectALoop is less complicated, but it's wrong. The only loop this will detect is if node 2i loops back onto node i. But the list could be 3 elements long looping onto the start; it could be lots of numbers that aren't 2i and i. Since there are probably a lot of numbers, way too many to try them all, you can't fix this strategy. There is no clever way to find cycles in a graph that is any faster or more intuitive than the one I wrote above. As far as I know.

Answer 2

Your removeLoop code is wrong, it never terminates:

let's assume this list:

A -> B -> C -> A

with loop length 3.

You correctly find the loop length, 3, you then set ptr1 and ptr2 to the head of the list, and then call .next on ptr2 for the length of the loop + 1 times (because of <=).

// for i = 0; i <= 3

A.next -> B // i = 0
B.next -> C // i = 1
C.next -> A // i = 2
A.next -> B // i = 33

So in the end you have ptr2 = B and ptr1 = A, i.e. ptr2 === ptr1.next!

One is the next of the other, and in the while loop you advance both until one is equal to the other, but they will never be, because they always be one the next of the other!

If you change the <= to just < it works, but the second while loop is actually useless.

Answer 3

This variable is messed up...

var looplen = 1,i;

It looks like you want it to be a 1.