Detecting loop in singly linked list

Problem

Identifying if there is any loop in singly linked list. Loop meaning any node connecting to one of the previous nodes.

Solution

• Best solution involves 2 traversal pointers – slow pointer which hops 1 node at a times and fast pointer which hops 2 nodes at a time. If they meet at any point, then there is a loop.
• This solutions works for finding if the singly linked list is circular or not. Circular, meaning, last node connecting to the first node in the list.
• Time complexity – O(n)
• Java based implementation along with its junit goes below.

package com.computepatterns.problemsolving.linkedlist;

/**
 * Detect loop in singly linked list.
 */
public class DetectingLoopLinkedList {
    /**
     * Represents nodes in the linked list.
     */
    public static class Node{
        private int value;
        private Node next;

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Node node = (Node) o;
            return value == node.value &&
                    com.google.common.base.Objects.equal(next, node.next);
        }

        @Override
        public int hashCode() {
            return com.google.common.base.Objects.hashCode(value, next);
        }

        public Node(int value) {
            this.value = value;
        }

        public int getValue() {
            return value;
        }

        Node getNext() {
            return next;
        }


        public void setNext(Node next) {
            this.next = next;
        }
    }

    private Node start;

    public void setStart(Node start) {
        this.start = start;
    }

    public boolean detectLoop(Node start){
        /* Declare slow and fast pointers */
        // Fast pointer jumps 2 nodes at a time.
        Node slowPtr = start, fastPtr = start;

        /* Traverse till end node is found */
        while(null != slowPtr || null != fastPtr){
            slowPtr = slowPtr.getNext();

            // Fast pointer hops 2 nodes at a time.
            if(null != fastPtr.getNext()) {
                fastPtr = fastPtr.getNext().getNext();
            }else {
                // Reached end of linked list.
                break;
            }

        /* If both the pointers point to the same node any time, then there is a loop */
            if(slowPtr == fastPtr){
                // Loop found.
                return true;
            }
        }

        return false;
    }
}

package com.computepatterns.problemsolving.linkedlist;

import static org.junit.Assert.assertEquals;

import org.junit.Test;

/**
 * Testing the algorithm of detecting loop in linked list.
 */
public class DetectingLoopLinkedListTest {

    @Test
    public void testDetectLoop_loop_scenario() throws Exception {

        DetectingLoopLinkedList.Node node1 = new DetectingLoopLinkedList.Node(1);
        DetectingLoopLinkedList.Node node2 = new DetectingLoopLinkedList.Node(2);
        DetectingLoopLinkedList.Node node3 = new DetectingLoopLinkedList.Node(3);
        DetectingLoopLinkedList.Node node4 = new DetectingLoopLinkedList.Node(4);
        DetectingLoopLinkedList.Node node5 = new DetectingLoopLinkedList.Node(5);
        DetectingLoopLinkedList.Node node6 = new DetectingLoopLinkedList.Node(6);
        DetectingLoopLinkedList.Node node7 = new DetectingLoopLinkedList.Node(7);

        node1.setNext(node2);
        node2.setNext(node3);
        node3.setNext(node4);
        node4.setNext(node5);
        node5.setNext(node6);
        node6.setNext(node7);
        node7.setNext(node3);


        // Loop is present.
       assertEquals(true, new DetectingLoopLinkedList().detectLoop(node1));
    }

    @Test
    public void testDetectLoop_no_loop_scenario() throws Exception {

        DetectingLoopLinkedList.Node node1 = new DetectingLoopLinkedList.Node(1);
        DetectingLoopLinkedList.Node node2 = new DetectingLoopLinkedList.Node(2);
        DetectingLoopLinkedList.Node node3 = new DetectingLoopLinkedList.Node(3);
        DetectingLoopLinkedList.Node node4 = new DetectingLoopLinkedList.Node(4);
        DetectingLoopLinkedList.Node node5 = new DetectingLoopLinkedList.Node(5);
        DetectingLoopLinkedList.Node node6 = new DetectingLoopLinkedList.Node(6);
        DetectingLoopLinkedList.Node node7 = new DetectingLoopLinkedList.Node(7);

        node1.setNext(node2);
        node2.setNext(node3);
        node3.setNext(node4);
        node4.setNext(node5);
        node5.setNext(node6);
        node6.setNext(node7);


        // Loop is present.
        assertEquals(false, new DetectingLoopLinkedList().detectLoop(node1));
    }
}

Link to the source code

References

• http://www.geeksforgeeks.org/write-a-c-function-to-detect-loop-in-a-linked-list/