Loop in linked list

Loop in linked list

Detect loop in linked list is very common linked list question which is asked in telephonic interview rounds. Problem statement is :

Given singly linked list, check if there is loop in linked list and if yes, find start node or point of the loop.

For example, if for linked list shown below, there is a loop in linked list and it start at node 8.

loop in linked list
Loop in linked list, starting node is 8

Loop in linked list : thoughts

What is difference between a normal singly linked list and a linked list with loop? If we traverse normal linked list, we are destined to encounter a node which is null, which in effect is the last node of normal linked list. However, in a linked list with a loop, we will never reach null and circle around in the loop.

Can we use this property to find if there is a loop or not in a linked list? If we move two pointers with different speeds,, the fast pointer, which moves two nodes at a time will reach to end of linked list before slow pointer, which moves one node at a time, in a normal list (without a loop). However, in list with loop, fast pointer will go around in circles and eventually, slow pointer will catch up with it. So, if ever, before fast pointer reaches null, slow pointer catches up with it, there is definitely a loop in linked list. This method of using fast and slow pointers to traverse linked list at different speeds is commonly known as hare and tortoise method and used in solving many problems on linked list like find middle of linked list, palindrome linked list etc.

Let’s take an example and see what we are thinking is correct. Below is a linked list with a loop, let’s see if slow and faster pointer ever meet.

We initialize slow as head(4) and fast as next of head(3).  fast moves two steps and hence reaches node 8, where as slow reaches at 3.

Since, fast is not null yet, we jump again, this time fast points to 7 and slow points to 5.

Again, fast is still not null, so we move again, fast now is at 8 and so is slow.

This is where we can safely say that there is a loop linked list.

    public boolean isLoop(){
        /* 
            Base condition if there is no nodes,
            return false
         */
        if(this.head == null){
            return false;
        }
        
        Node slow = this.head;
        Node fast = slow.getNext(); // slow cannot be null here
        
        while(fast != null && fast != slow){
            /*
            Move faster ponter two nodes at a time.
             */
            fast = fast.getNext();
            if(fast == null) return false;
            
            fast = fast.getNext();
            //Slow pointer moves one node at a time
            if(slow != null) { slow = slow.getNext(); }
        }
        
        return fast == slow;
    }

There is common mistake which happens is to check content of fast and slow pointers to see if there are at the same node. This will fail when there are duplicate values in different nodes. To avoid wrongly predicting nodes being equal when actually content is equal, compare node addresses and not content.

Start of loop in linked list

This problem is interesting and require a bit of thinking. Can we find number of nodes in loop?
Starting from node fast and slow met at, move fast two nodes at a time and slow one node at a time, they will again meet at the same node. Keep count of how many nodes slow pointer moved, it will give length of loop. You can try with different length loops and see that it is actually true.

private int getNumNodesInLoop(Node slow){

        Node fast = slow;
        int count = 0;

        do{
            /*
            Move faster pointer two nodes at a time.
            As we are sure that there is loop in LL at this
            point, fast cannot be null. That's why it is
            removed from the while loop condition too.
             */
            fast = fast.getNext();
            fast = fast.getNext();
            //Slow pointer moves one node at a time
            if(slow != null) {
                slow = slow.getNext();
                count++;
            }
        }while(fast != slow);

        return count;
    }

Now, we have number of nodes in loop, let’s say k. How can we find starting node of loop. We take two pointers again, fast and slow, fast is k nodes ahead of slow which is at head of list. Why? Hypothesis is that if we move them with same speed, when slow reaches start of loop, fast would have finished traversing k loop nodes and will also be at the start of loop. So, with fast ahead of slow by k nodes, when both meet, that node should be start of loop in linked list.

Start of loop in linked list implementation

package com.company;

/**
 * Created by sangar on 14.10.18.
 */
public class LinkedList<T> {
    private Node<T> head;

    public LinkedList(){
        head = null;
    }

    public void insert(T data){
        //If this is the first node to insert
        if(this.head == null){
            this.head = new Node<>(data);
        }
        else{
            Node current = this.head;
            /* Defensive programming, just in case current is null
            * As we check null condition for head earlier,
			it should not be null in this while loop ever though
            * */
            while(current != null && current.getNext() != null){
                current = current.getNext();
            }
            //We are at the last node.
            current.setNext(new Node(data));
        }
    }

    public Node getLastNode(){

        if(this.head == null){
            return null;
        }
        else{
            Node current = this.head;

            while(current != null && current.getNext() != null){
                current = current.getNext();
            }
            return current;
        }
    }

    public Node<T> get(T data){
        /*
            Base condition if there is no nodes,
            return null
         */
        if(this.head == null){
            return null;
        }
        else{
            Node current = this.head;
            /* Defensive programming, just in case current is null
            * As we check null condition for head earlier, it
			should not be null in this while loop ever though
            * */
            while(current != null && current.getData() != data){
                current = current.getNext();
            }

            return current;
        }
    }

    /* As we need slow pointer to get number
    of nodes again, we will return slow pointer
    rather than boolean
     */
    private Node isLoop(){
        /*
            Base condition if there is no nodes,
            return false
         */
        if(this.head == null){
            return null;
        }

        Node slow = this.head;
        Node fast = slow.getNext(); // slow cannot be null here

        while(fast != null && fast != slow){
            /*
            Move faster pointer two nodes at a time.
             */
            fast = fast.getNext();
            if(fast == null) return null;

            fast = fast.getNext();
            //Slow pointer moves one node at a time
            if(slow != null) { slow = slow.getNext(); }
        }

        return fast == slow ? slow : null;
    }

    private int getNumNodesInLoop(Node slow){

        Node fast = slow;
        int count = 0;

        do{
            /*
            Move faster pointer two nodes at a time.
            As we are sure that there is loop in LL at this
            point, fast cannot be null. That's why it is
            removed from the while loop condition too.
             */
            fast = fast.getNext();
            fast = fast.getNext();
            //Slow pointer moves one node at a time
            if(slow != null) {
                slow = slow.getNext();
                count++;
            }
        }while(fast != slow);

        return count;
    }

    public Node getStartNodeLoop(){

        Node slow = isLoop();

        /* If slow is not null, it means there is a loop */
        if(slow != null){
            int k = getNumNodesInLoop(slow);

            slow = this.head;

            //Give fast head start of k nodes.
            Node fast = slow;
            while(k-- > 0 && fast != null){
                fast = fast.getNext();
            }

            while(fast != slow){
                slow = slow.getNext();
                fast = fast.getNext();
            }
        }
        return slow;
    }
}

Test cases for finding loop in linked list implementation

package test;

import com.company.LinkedList;
import com.company.Node;
import org.junit.jupiter.api.Test;
import static org.junit.jupiter.api.Assertions.assertEquals;

/**
 * Created by sangar on 23.9.18.
 */
public class LoopInLinkedListTest {

    LinkedList<Integer> tester = new LinkedList<>();
    @Test
    public void loopPresentTest() {

        tester.insert(4);
        tester.insert(3);
        tester.insert(5);
        tester.insert(8);
        tester.insert(9);
        tester.insert(7);
        tester.insert(10);

        //Created a loop
        Node loopNode = tester.get(8);
        tester.getLastNode().setNext(loopNode);

        assertEquals(loopNode, tester.getStartNodeLoop());
    }

    @Test
    public void loopAbsentTest() {

        tester.insert(4);
        tester.insert(3);
        tester.insert(5);
        tester.insert(8);
        tester.insert(9);
        tester.insert(7);
        tester.insert(10);

        assertEquals(null, tester.getStartNodeLoop());
    }

    @Test
    public void EmptyLinkedListTest() {
        assertEquals(null, tester.getStartNodeLoop());
    }

    @Test
    public void OneNodeLoopTest() {
        tester.insert(4);

        //Created a loop
        Node loopNode = tester.get(4);
        tester.getLastNode().setNext(loopNode);

        assertEquals(loopNode, tester.getStartNodeLoop());
    }

    @Test
    public void loopBackToHeadTest() {
        tester.insert(4);
        tester.insert(3);
        tester.insert(5);
        tester.insert(8);
        tester.insert(9);
        tester.insert(5);
        tester.insert(7);


        //Created a loop
        Node loopNode = tester.get(4);
        tester.getLastNode().setNext(loopNode);

        assertEquals(loopNode, tester.getStartNodeLoop());
    }
}

Complexity to find a loop in linked list is O(n) as we have to scan all node of linked list at least once.

Please share if there is something wrong or missing.

Reference : cslibrary.stanford.edu/103/LinkedListBasics.pdf