Find the starting point of the Loop of LinkedList

Dec 18, 2024 • 3 mins read

Problem Overview

The LeetCode problem "Linked List Cycle II" is a classic question that combines the concepts of linked lists and cycle detection. The problem requires us to determine if a cycle exists in a linked list and, if so, return the node at the start of the cycle.

Problem Statement:
Given the head of a linked list, return the node where the cycle begins. If there is no cycle, return null.

Link: Linked List Cycle II

Constraints:

The number of nodes in the list is in the range [0, 10^4].
-10^5 <= Node.val <= 10^5
pos is the position in the list (0-indexed) where the tail connects to form a cycle. pos is -1 if there is no cycle.

Understanding the Problem

The problem is centered around detecting cycles in a linked list and then tracing back to the start of the cycle. In simpler terms, if you're traversing a linked list and you find that a node points back to a node that has already been seen, you have detected a cycle.

Key DSA Concepts and Theory

Linked List

A linked list is a data structure consisting of nodes where each node contains a value and a pointer to the next node. There are typically two types of linked lists:

Singly Linked List: Each node points to the next node and the last node points to null.
Doubly Linked List: Each node has pointers to both the next node and the previous node.

Cycle in Linked List

A cycle in a linked list occurs when a node's next pointer points to any of the previous nodes in the list, thus creating a loop or cycle. Detecting a cycle efficiently requires understanding cycle detection algorithms.

Floyd’s Cycle Detection Algorithm

Also known as the Tortoise and Hare algorithm, it uses two pointers moving at different speeds (slow and fast). The essence of this algorithm is simple:

Slow Pointer: Moves one step at a time.
Fast Pointer: Moves two steps at a time.

If there is a cycle, the fast pointer will meet the slow pointer inside the cycle. This technique is effective for cycle detection with a time complexity of O(n).

Solution Approach

Step-by-Step Explanation

To solve this problem, we use the Floyd’s Cycle Detection Algorithm. Here's the detailed step-by-step approach:

Detect if a Cycle Exists: Use the slow and fast pointer approach.
- Initialize both slow and fast pointers at the head.
- Move the slow pointer by one step and the fast pointer by two steps.
- If they meet, then a cycle exists. If the fast pointer reaches the end (null), there's no cycle.
Find the Entry Point of the Cycle:
- Once a cycle is detected, we need to locate the cycle's start. Reset one pointer to the head and move both pointers one step at a time. The point at which they meet is the starting node of the cycle.

Below is the implementation in C++ and Java:

C++ Implementation

#include <iostream>

class ListNode {
public:
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if (!head || !head->next) {
            return nullptr;
        }
        
        ListNode *slow = head;
        ListNode *fast = head;
        
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast) { // Cycle detected
                ListNode *entry = head;
                while (entry != slow) {
                    entry = entry->next;
                    slow = slow->next;
                }
                return entry; // Start of the cycle
            }
        }
        
        return nullptr; // No cycle
    }
};

Java Implementation

public class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
        next = null;
    }
}

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null) {
            return null;
        }

        ListNode slow = head;
        ListNode fast = head;

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

            if (slow == fast) {
                ListNode entry = head;
                while (entry != slow) {
                    entry = entry.next;
                    slow = slow.next;
                }
                return entry;
            }
        }

        return null;
    }
}

Time and Space Complexity Analysis

Time Complexity: O(n)
Both pointers traverse the list at most twice, leading to linear complexity.
Space Complexity: O(1)
The algorithm uses a constant amount of extra space, as only a fixed number of pointers are used.

Common Mistakes to Avoid

Missing Edge Cases: Ensure to check and handle cases like an empty list or a list with only one node.
Pointer Initialization: Improper initialization of fast and slow pointers can lead to logical errors or infinite loops.
Cycle Detection Conditions: Failing to properly check conditions in while loops can lead to runtime errors, especially when accessing fast->next.

Additional Resources and References

To further enhance your understanding of the topic, you might want to explore the following resources:

The above articles and videos provide in-depth exploration and implementation tips for working with linked lists and cycle detection algorithms.

Terms & Conditions Privacy Policy Refund Policy