Linked List Cycle in Java (Time Complexity: O(n), Space Complexity: O(1))

Given head, the head of a linked list, determine if the linked list has a cycle in it.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to. Note that pos is not passed as a parameter.

Return true if there is a cycle in the linked list. Otherwise, return false.

Example 1:

Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).

Example 2:

Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 0th node.

Example 3:

Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.

Constraints:

The number of the nodes in the list is in the range [0, 10⁴].
-10⁵ <= Node.val <= 10⁵
pos is -1 or a valid index in the linked-list.

Follow up: Can you solve it using O(1) (i.e. constant) memory?

Understanding the Problem

The core challenge of this problem is to detect if a linked list contains a cycle. A cycle occurs when a node's next pointer points back to a previous node, creating a loop. This problem is significant in various applications, such as detecting infinite loops in algorithms or ensuring data integrity in linked data structures.

Potential pitfalls include misunderstanding the problem constraints or failing to handle edge cases, such as an empty list or a single node pointing to itself.

Approach

To solve this problem, we can use multiple approaches:

Naive Solution

A naive solution involves using a hash set to keep track of visited nodes. As we traverse the list, we check if the current node is already in the set. If it is, we have detected a cycle. Otherwise, we add the node to the set and continue. This approach has a time complexity of O(n) but a space complexity of O(n), which is not optimal.

Optimized Solution: Floyd's Tortoise and Hare Algorithm

A more efficient solution is Floyd's Tortoise and Hare algorithm, which uses two pointers moving at different speeds. The slow pointer (tortoise) moves one step at a time, while the fast pointer (hare) moves two steps at a time. If there is a cycle, the fast pointer will eventually meet the slow pointer. This approach has a time complexity of O(n) and a space complexity of O(1).

Algorithm

Here is a step-by-step breakdown of Floyd's Tortoise and Hare algorithm:

Initialize two pointers, slow and fast, both pointing to the head of the list.
Move the slow pointer one step at a time and the fast pointer two steps at a time.
If the fast pointer reaches the end of the list (i.e., null), there is no cycle, and we return false.
If the slow pointer and fast pointer meet, there is a cycle, and we return true.

Code Implementation

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        // Initialize two pointers, slow and fast
        ListNode slow = head;
        ListNode fast = head;
        
        // Traverse the list with two pointers
        while (fast != null && fast.next != null) {
            slow = slow.next; // Move slow pointer one step
            fast = fast.next.next; // Move fast pointer two steps
            
            // Check if the two pointers meet
            if (slow == fast) {
                return true; // Cycle detected
            }
        }
        
        return false; // No cycle detected
    }
}

Complexity Analysis

The time complexity of Floyd's Tortoise and Hare algorithm is O(n) because each pointer traverses the list at most once. The space complexity is O(1) because we only use two additional pointers, regardless of the list size.

Edge Cases

Consider the following edge cases:

An empty list (head is null): The function should return false.
A single node pointing to itself: The function should return true.
A list with no cycle: The function should return false.

These cases are handled effectively by the algorithm as it checks for null pointers and pointer equality.

Testing

To test the solution comprehensively, consider the following test cases:

head = [3,2,0,-4], pos = 1 (Expected output: true)
head = [1,2], pos = 0 (Expected output: true)
head = [1], pos = -1 (Expected output: false)
head = [], pos = -1 (Expected output: false)

Use a testing framework like JUnit to automate these tests and ensure the solution works as expected.

Thinking and Problem-Solving Tips

When approaching such problems, consider the following tips:

Understand the problem constraints and edge cases.
Think about different approaches and their trade-offs.
Start with a simple solution and then optimize it.
Practice similar problems to improve problem-solving skills.

Conclusion

Detecting a cycle in a linked list is a common problem with practical applications. Understanding and implementing Floyd's Tortoise and Hare algorithm provides an efficient solution with O(n) time complexity and O(1) space complexity. Practice and familiarity with such algorithms are crucial for improving problem-solving skills.

Additional Resources

For further reading and practice, consider the following resources: