Leetcode 141. Linked List Cycle

Problem Explanation

This problem involves determining if a given linked list has a cycle. A cycle in a linked list is when there exists a node in the list such that the next pointer of this node points back to one of the previous nodes creating a loop.

In this given problem, we use an integer pos to represent the position (0-indexed) in the linked list where the tail connects to. If pos is -1, it means there is no cycle in the linked list.

For example, consider the linked list: [3, 2, 0, -4], and pos is 1. The tail of this linked list connects to the node at position 1 (node with value 2). Hence, this linked list has a cycle and our function should return True.

Approach of the Solution

To solve this problem, we will use a two-pointer approach where one pointer moves slower (slow), advancing one step at a time, and the other pointer moves faster (fast), advancing two steps at a time.

We start both pointers at the beginning of the linked list. If the linked list has a cycle, the fast pointer will eventually catch up to the slow pointer (because it's moving twice as fast). When this happens, we return True, indicating that there's a cycle.

If the fast pointer reaches null (end of the linked list) before catching up to the slow pointer, then no cycle exists, so we return False.

Python Solution

1
2python
3class Solution:
4    def hasCycle(self, head):
5        slow, fast = head, head
6        while fast and fast.next:
7            slow = slow.next
8            fast = fast.next.next
9            if slow == fast:
10                return True  # Detected a cycle
11        return False  # Reached end of list without detecting a cycle

Java Solution

1
2java
3public class Solution {
4    public boolean hasCycle(ListNode head) {
5        ListNode slow = head, fast = head;
6        while (fast != null && fast.next != null) {
7            slow = slow.next;
8            fast = fast.next.next;
9            if (slow == fast) return true;  // Detected a cycle
10        }
11        return false;  // Reached end of list without detecting a cycle
12    }
13}

JavaScript Solution

1
2javascript
3var hasCycle = function(head) {
4    if(head===null) return false;
5    let slow = head;
6    let fast = head;
7    while(fast!==null && fast.next!==null) {
8        slow = slow.next;
9        fast = fast.next.next;
10        if(slow===fast) return true;  // Detected a cycle
11    }
12    return false;  // Reached end of list without detecting a cycle
13};

C++ Solution

1
2cpp
3class Solution {
4public:
5    bool hasCycle(ListNode *head) {
6        ListNode *slow = head, *fast = head;
7        while (fast && fast->next) {
8            slow = slow->next;
9            fast = fast->next->next;
10            if (slow == fast) return true;  // Detected a cycle
11        }
12        return false;  // Reached end of list without detecting a cycle
13    }
14};

C# Solution

1
2csharp
3public class Solution {
4    public bool HasCycle(ListNode head) {
5        if(head==null) return false;
6        ListNode slow = head, fast = head;
7        while(fast.next!=null && fast.next.next!=null) {
8            slow = slow.next;
9            fast = fast.next.next;
10            if(slow == fast) return true;  // Detected a cycle
11        }
12        return false;  // Reached end of list without detecting a cycle
13    }
14}

These solutions all implement the same algorithm and maintain the same space and time complexity. The space complexity is O(1), since we only use a constant amount of space. The time complexity is O(n), where n is the number of elements in the linked list. Take note that the solution presented runs on the assumption that the linked list's node has a next attribute or method that points to the next node in the linked list. So, to use this solution in your respective programming language, you have to ensure your linked list's node struct or class has a next attribute or method that fits this explanation.

While these solutions efficiently identify a cycle in a linked list, it's essential to understand that they are not able to identify the node where the cycle starts. This solution is often referred to as the "hare and tortoise" algorithm, as it involves two pointers moving at different speeds.

As per the problem statement, if the fast pointer (the hare) ever equals the slow pointer (the tortoise), that's our cue that a cycle is present. With no cycle, the hare (fast pointer) will eventually reach the end of the linked list. It's also pertinent to note that this algorithm doesn't necessarily work if there are multiple cycles in the linked list.

In conclusion, the ability to identify a cycle in a linked list is a fundamental skill, and understanding the "hare and tortoise" approach provides a useful and efficient solution. The idea of using two pointers moving at different speeds can also be applied to other common algorithmic problems as well.

Using coding logic to tackle such problems helps in enabling a greater understanding of how data structures work. This not only boosts problem-solving skills, but also aids clear, logical thinking when faced with other complex, real-world issues.