Detect a loop in LinkedList

May 21, 2018 by Sandeep Bhardwaj | Tags: Datastructure & Algorithms

Detect loop in a linked list.

Floyd’s Cycle-Finding Algorithm:

Traverse linked list using two pointers. Move one pointer(slowPtr) by one and other pointer(fastPtr) by two. If these pointers meet at some node then there is a loop. If pointers do not meet then linked list doesn’t have loop.

LinkedList.java

public class LinkedList<E> {
	static class Node<E> {
		E data;
		Node<E> next;

		Node(E data, Node<E> next) {
			this.data = data;
			this.next = next;
		}
	}// end of node class

	private Node<E> head = null;

	Node<E> getHead() {
		return head;
	}

	public void add(E e) {
		Node<E> node = new Node<>(e, null);
		if (head == null) {
			head = node;
		} else {
			Node<E> current = head;
			while (current.next != null) {
				current = current.next;
			}
			current.next = node;
		}
	}

	public void display(Node<E> head) {
		Node<E> current = head;
		while (current != null) {
			System.out.print(current.data + "-> ");
			current = current.next;
		}
		System.out.print("NULL\n");
	}

	public boolean detectLoop(Node<E> head) {
		Node<E> slowPtr = head;
		Node<E> fastPtr = head;
		while (fastPtr != null && fastPtr.next != null) {
			slowPtr = slowPtr.next;
			fastPtr = fastPtr.next.next;
			if (slowPtr == fastPtr) {
				return true;
			}
		}
		return false;
	}

	/**
	 * <pre>
	 * 1 > 2 > 3 > 4
	 *     ^       ^
	 *     |_______|
	 *
	 * </pre>
	 *
	 * @author Sandeep Bhardwaj
	 *
	 */
	public static void main(String[] arg) {
		LinkedList<Integer> list = new LinkedList<>();
		list.add(1);
		list.add(2);
		list.add(3);
		list.add(4);
		Node<Integer> head = list.getHead();
		//create loop
		head.next.next.next = head.next;
		list.display(head);
	}
}

Output

Loop found ...

Complexity

Time Complexity: O(n)
Auxiliary Space: O(1)