How to find if the Linked List contains any Cycle/Loop

Carvia Tech | December 11, 2017 | 2 min read | 22 views


DetectCycle in LinkedList using two pointers.

This solution is “Floyd’s Cycle-Finding Algorithm” as published in “Non-deterministic Algorithms” by Robert W. Floyd in 1967. It is also called “The Tortoise and the Hare Algorithm”.

O(n) time complexity

Simultaneously go through the list by ones (slow iterator) and by twos (fast iterator). If there is a loop the fast iterator will go around that loop twice as fast as the slow iterator. The fast iterator will lap the slow iterator within a single pass through the cycle. Detecting a loop is then just detecting that the slow iterator has been lapped by the fast iterator.

Algorithm Steps

  1. Use two pointers fast and slow

  2. Move fast two nodes and slow one node in each iteration

  3. If fast and slow meet then linked list contains cycle

  4. if fast points to null or fast.next points to null then linked list is not cyclic

Java Source Code

public class CycleFreeLinkedList<T> {
    private Node<T> first;
    private Node<T> last;

    public CycleFreeLinkedList() {
        first = new Node<>();
    }

    public void appendToTail(T data) {
        final Node l = last;
        final Node<T> newNode = new Node(data);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
    }

    public void appendNodeToTail(Node<T> node) {
        final Node l = last;
        final Node<T> newNode = node;
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
    }

    public void detectCyclic() {
        Node fast = first;
        Node slow = first;

        while (fast != null && fast.getNext() != null) {
            fast = fast.getNext().getNext();
            slow = slow.getNext();

            //if fast and slow pointers are meeting then LinkedList is cyclic
            if (fast == slow) {
                throw new CyclicNodeException(fast.toString());
            }
        }
    }

    @Override
    public String toString() {
        detectCyclic();
        StringBuilder output = new StringBuilder();
        Node current = first.getNext();
        while (current != null) {
            output.append(current).append(" -> ");
            current = current.getNext();
        }
        return output.toString();
    }

    public static class Node<T> {
        Node next;
        T data;

        public Node() {
        }

        public Node(T data) {
            this.data = data;
        }

        public Node getNext() {
            return next;
        }

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

        public T getData() {
            return data;
        }

        public void setData(T data) {
            this.data = data;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "data=" + data +
                    '}';
        }
    }

    public static class CyclicNodeException extends RuntimeException {

        public CyclicNodeException(String msg) {
            super("There is a cyclic node in the list at - " + msg);
        }
    }
}

Unit Test to detect Loops/Cycle

public class CycleFreeLinkedListTest {

    @Rule
    public ExpectedException thrown= ExpectedException.none();

    @org.junit.Test
    public void testIsNotCyclic() throws Exception {
        CycleFreeLinkedList<String> linkedList = new CycleFreeLinkedList();
        linkedList.appendToTail("101");
        linkedList.appendToTail("201");
        linkedList.appendToTail("301");
        linkedList.appendToTail("401");

        System.out.println("linkedList = " + linkedList);
    }

    @org.junit.Test
    public void testIsCyclic() throws Exception {
        CycleFreeLinkedList<String> linkedList = new CycleFreeLinkedList();
        linkedList.appendToTail("101");

        Node<String> cycle = new Node<>("201");

        linkedList.appendNodeToTail(cycle);
        linkedList.appendToTail("301");
        linkedList.appendToTail("401");
        linkedList.appendNodeToTail(cycle);

        thrown.expect( CyclicNodeException.class );
        thrown.expectMessage("There is a cyclic node in the list at - Node{data=401}");

        System.out.println("linkedList = " + linkedList);
    }
}

Top articles in this category:
  1. Difference between HashMap, LinkedHashMap and TreeMap
  2. Given a collection of 1 million integers, All ranging between 1 to 9, how would you sort them in Big O(n) time
  3. How will you implement a Blocking Queue in Java
  4. What is difference between Vector and ArrayList, which one shall be preferred
  5. What is Deadlock in Java? How to troubleshoot and how to avoid deadlock
  6. Removing elements while iterating over a Java Collection
  7. Find missing numbers in 4 billion unique numbers with 50MB RAM


Find more on this topic:
Core Java image
Core Java

Core Java - OOP Concepts, Garbage Collection, Multi-threading, Collections Framework, Java 8 Features, Lambda Functions, Streams.

Last updated 1 week ago


Recommended books for interview preparation:

This website uses cookies to ensure you get the best experience on our website. more info