/ Linked List

Check if a LinkedList has a cycle

Problem Statement

Given a single linked list, verify if the list has a cycle.
A linked list has a cycle if a node's reference points back to an earlier node in the chain.
Example:
1 -> 2 -> 3 -> 4 -> 5
↑ _ _ _ _ ↓


Solution Explanation

Typically in a single linked list each node has a reference to a node forward in the chain, so every node can be visited only once in the chain, but if there's a cycle in the list, you will come across nodes more than once during the traversal.

Since we will be looking for a node which is visited twice, you can use a map to store all the visited nodes, and whenever there's a node which is already in the map, you can return true saying there's a cycle.

But this involves using additional space for the map or set. We can avoid this and detect if there exists a cycle simply by using an additional pointer which traverses the lists twice the speed as the regular list pointer.

Below is the java implementation of detecting cycle in linked lists,

public class LinkedListCycle {
    public boolean doesCycleExist(ListNode head) {
      if(head==null) return false;
      ListNode walker = head, runner = head;
      while(runner.next!= null && runner.next.next!=null){
          walker = walker.next;
          runner = runner.next.next;
          if(walker==runner){
              return true;
          }
      }
        return false;
    }
}
Time Complexity

The time complexity is O(n) since we do a single traversal across the list.