Detect a cycle in Linked List

Problem Overview

The problem "Linked List Cycle" on LeetCode involves detecting cycles within a linked list. The task is to determine if a given linked list contains a cycle, meaning that there's a node in the list that can be reached again by continuously following the next pointers.

URL: LeetCode - Linked List Cycle

The input provided is the head of the linked list, and the output should be a boolean value, true if there is a cycle in the list, otherwise false.

Understanding the Problem

In the context of linked lists, a cycle occurs when a node's next pointer points back to a previous node in the list, creating a loop. A typical linked list ends with a null value, but in a cyclical linked list, a node points back to a previously traversed node, causing an infinite loop.

To solve the problem, the task is to efficiently determine whether such a loop exists. A straightforward way to solve this is to traverse the list and keep track of visited nodes, but this could potentially use extra memory for every node.

Key DSA Concepts and Theory

Linked List

A linked list is a linear data structure where each element, called a node, contains a data part and a reference (or a pointer) to the next node in the sequence. Linked lists are often used due to their efficient, memory-friendly nature of insertion and deletion operations.

Cycle Detection

Cycle detection is a common problem in the study of data structures and algorithms. The "Tortoise and Hare" or two-pointer technique is often used to detect cycles in linked lists efficiently, without the need for extra space.

Tortoise and Hare (Floyd's Cycle Detection Algorithm)

This algorithm uses two pointers, one moving slowly (tortoise) and one moving fast (hare). The slow pointer advances one node at a time, while the fast pointer advances two nodes. If there is a cycle, the fast pointer will eventually meet the slow pointer. If there is no cycle, the fast pointer will reach the end of the list (null).

Solution Approach

We'll use the Tortoise and Hare algorithm to solve this problem. This approach is both time-efficient and space-efficient.

Step-by-step Solution

1. Initialize Pointers:

   • Start with two pointers, slow and fast, both initialized to the head of the linked list.

2. Traverse the List:

   • Move the slow pointer by one step.
   • Move the fast pointer by two steps.

3. Cycle Detection:

   • If there is a cycle, at some point slow and fast will meet.
   • If fast reaches null or the next node of fast is null, the list has no cycle.

4. Return Result:

   • Return true if the two pointers meet; otherwise, return false if fast reaches the end of the list.

Code Implementation

C++

class Solution {
public:
    bool hasCycle(ListNode *head) {
        if (!head || !head->next) return false;
        
        ListNode* slow = head;
        ListNode* fast = head;
        
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
            
            if (slow == fast) return true;
        }
        
        return false;
    }
};

Java

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

Time and Space Complexity Analysis

• Time Complexity: O(n), where n is the number of nodes in the linked list. Each node is visited at most once by each pointer.
• Space Complexity: O(1), since only a couple of pointers are used, regardless of the input size.

Common Mistakes to Avoid

1. Ignoring Edge Cases:

   • Ensure to handle cases where the list is empty (head is null) or has only one node (head->next is null) as they cannot form a cycle.

2. Incorrect Pointer Movement:

   • Make sure to advance the fast pointer two steps ahead and slow only one step to use the Tortoise and Hare method correctly.

Similar Problems on LeetCode

Here are some similar problems that you might want to try:

1. Linked List Cycle II (Problem 142): Detect and find the starting node of the cycle.
2. Intersection of Two Linked Lists (Problem 160): Determine if two singly linked lists intersect and find the intersection node.

Additional Resources and References

• Introduction to Cycle Detection in Linked Lists
• MIT Lecture Notes on Linked Lists

These resources can provide additional explanations and deeper insights into cycle detection and linked lists concepts, further helping solidify understanding of these data structure applications.