Detect Loop in Linked List

Problem Statement

Given a linked list. Determine if the linked list has a cycle in it.

A linked list contains a cycle if it consists of a node that can be reached again by continuously following the next pointer.

Examples:

Input: 

Output: True
Explanation:

The linked list consists of a loop, where the last node connects to the second node.

Input: 

Output: True

HashSet Approach

The simplest approach to solve this problem is to check whether a node in the linked list has been visited before. To perform this operation, a hashmap can be used.

Algorithm

• Initialise a hashmap.
• Traverse the linked list till the head pointer isn’t NULL:
  • If the current node is already present in the hashset, it ensures that the linked list contains a loop. Hence, terminate and return True.
  • Else, continue traversing and continue inserting the node into the hashset.
• Return False if it doesn’t satisfy the above conditions.

C++ Implementation

bool hasCycle(Node* head) {
        set<Node*> mp;
        while (head != null) {
            if (mp.find(head) != mp.end()) {
                return true;
            }
            mp[head]++;
            head = head->next;
        }
        return false;
    }

Java Implementation

 public boolean hasCycle(ListNode head) {
        Set<ListNode> mp = new HashSet<>();
        while (head != null) {
            if (mp.contains(head)) {
                return true;
            }
            mp.add(head);
            head = head.next;
        }
        return false;
    }

Python Implementation

def hasCycle(head):
        mp = set()
        while head is not None:
            if head in mp:
                return True
            mp.add(head)
            head = head.next
        return False

Time Complexity: O(N) where N is the number of nodes of the linked list.
Space Complexity: O(N), as HashSet is used

Floyd’s Cycle Detection Algorithm

This approach uses a two-pointer – a fast pointer and a slow pointer to determine if there exists a cycle in the loop. The slow pointer moves one node ahead at a time, while the fast pointer moves two nodes ahead at a time.
If a loop exists in the linked list, the fast and slow pointers are bound to meet at some point.

Algorithm: 

• Initialise two pointers, fast and slow to the head of the linked list.
• Traverse through the linked list until the fast pointer doesn’t reach the end of the linked list.
• If the fast pointer reaches the end, it means that the linked list doesn’t contain any cycle. Hence, return False.
• Else, move the slow pointer by one node i.e. slow = slow -> next and fast pointer by two nodes i.e. fast = fast -> next -> next.
• At any point, if the fast and the slow pointers point to the same node, return True as a loop has been detected.

C++ Code for Two Pointer Approach

bool hasCycle(ListNode *head) {
        if (head == NULL) 
            return false;
        
        ListNode *slow = head;
        ListNode* *fast = head;
        
        while (slow != fast) {
            if (fast == Null || fast->next == NULL) {
                return false;
            }
            slow = slow->next;
            fast = fast->next->next;
        }
        return true;
    }

Java Code for Two Pointer Approach

public boolean hasCycle(ListNode head) {
        if (head == null) {
            return false;
        }
 
        ListNode slow = head;
        ListNode fast = head.next;
        while (slow != fast) {
            if (fast == null || fast.next == null) {
                return false;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        return true;
    }

Python Code for Two Pointer Approach

def hasCycle(self, head: ListNode) -> bool:
        if head is None:
            return False
        slow = head
        fast = head.next
        while slow != fast:
            if fast is None or fast.next is None:
                return False
            slow = slow.next
            fast = fast.next.next
        return True

Time Complexity: O(N), where N is the number of nodes of the linked list.
Space Complexity: O(1), as a map is used.

Practice Question

List Cycle

Frequently Asked Questions

How do you detect a loop in a linked list?
A loop can be detected efficiently using the fast and slow pointer algorithm, where the fast pointer moves by two nodes and the slow pointer move by one node at a time.

Will the fast and slow pointer always meet at some point if the list contains a cycle?
Yes, if the linked list contains a cycle, the fast and slow pointer will always meet at some point.

Additional Resources

• Detect Loop in Linked List
• Reverse a Linked List
• Add Two Numbers Represented by Linked Lists
• Intersection of Two Linked Lists
• Linked List Interview Questions
• Linked List MCQ
• Application of Linked List
• Types of Linked List