{x}
blog image

Linked List Cycle

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, 104].
  • -105 <= Node.val <= 105
  • pos is -1 or a valid index in the linked-list.

 

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

141. Linked List Cycle

This problem asks to determine if a given linked list contains a cycle. A cycle exists if a node can be reached again by repeatedly following the next pointer.

Approach 1: Hash Table

This approach uses a hash table (or set) to store visited nodes. We iterate through the linked list, adding each node to the hash table. If we encounter a node that's already in the hash table, it means we've encountered this node before, indicating a cycle.

Code: (Python example)

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        visited = set()
        curr = head
        while curr:
            if curr in visited:
                return True  # Cycle detected
            visited.add(curr)
            curr = curr.next
        return False  # No cycle

Time Complexity: O(N), where N is the number of nodes in the linked list. We visit each node at most once.

Space Complexity: O(N) in the worst case (no cycle), as we might store all nodes in the visited set.

Approach 2: Fast and Slow Pointers (Floyd's Tortoise and Hare Algorithm)

This is a more efficient approach using only constant extra space. We use two pointers:

  • slow: moves one step at a time.
  • fast: moves two steps at a time.

If there's a cycle, the fast pointer will eventually lap the slow pointer. If there's no cycle, the fast pointer will reach the end of the list.

Code: (Python example)

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                return True  # Cycle detected
        return False  # No cycle

Time Complexity: O(N). In the worst case (no cycle), the fast pointer traverses the entire list.

Space Complexity: O(1). We use only two pointers.

Code in Other Languages

The fast and slow pointer approach is generally preferred due to its better space complexity. Here are examples in other languages:

Java:

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

C++:

bool hasCycle(ListNode *head) {
    ListNode *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return true;
    }
    return false;
}

JavaScript:

var hasCycle = function(head) {
    let slow = head;
    let fast = head;
    while(fast !== null && fast.next !== null){
        slow = slow.next;
        fast = fast.next.next;
        if(slow === fast) return true;
    }
    return false;
};

Go:

func hasCycle(head *ListNode) bool {
    slow, fast := head, head
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
        if slow == fast {
            return true
        }
    }
    return false
}

These examples all follow the same logic as the Python example using the fast and slow pointer technique. Remember to define the ListNode structure appropriately for your chosen language.