Detect Loop in Linked List

Table Of Contents

show

Problem Statement
HashSet Approach

C++ Implementation
Java Implementation
Python Implementation

Floyd’s Cycle Detection Algorithm

C++ Code for Two Pointer Approach
Java Code for Two Pointer Approach
Python Code for Two Pointer Approach

Practice Question
Frequently Asked Questions

Q.1: How do you detect a loop in a linked list?
Q.2: Will the fast and slow pointer always meet at some point if the list contains a cycle?

Additional Resources

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

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

Java Code for Two Pointer Approach

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

Python Code for Two Pointer Approach

// PYTHON Code
def hasCycle(self, head: ListNode) -> bool:
        if head is None:
            return False
        slow = head
        fast = head.next
        while True:
            if fast is None or fast.next is None:
                return False
            slow = slow.next
            fast = fast.next.next
            if(slow == fast)
                return True
        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

Q.1: How do you detect a loop in a linked list?

Ans: 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.

Q.2: Will the fast and slow pointer always meet at some point if the list contains a cycle?

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