Linked List Exercise (2) - Linked List Cycle

https://leetcode.com/problems/linked-list-cycle/description/

Entire Code

# Definition for singly-linked list.
class Node(object):
    def __init__(self, value):
        self.value = value
        self.next = None

def create_linked_list(values):
    if not values:
        return None, None

    head = Node(values[0])
    tail = head

    for value in values[1:]:
        tail.next = Node(value)
        tail = tail.next

    return head, tail

class Solution(object):
    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        slow = head
        fast = head

        while fast is not None and fast.next is not None:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                return True
        return False

Key code

class Solution(object):
    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        slow = head
        fast = head

        # Traverse the list with two pointers moving at different speeds
        while fast is not None and fast.next is not None:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                return True  # A cycle is detected
        return False  # No cycle detected

The hasCycle method is designed to detect whether a linked list contains a cycle (loop). A cycle in a linked list means that a node’s next pointer references an earlier node in the list, creating an infinite loop. This method uses a two-pointer approach, known as Floyd’s Cycle-Finding Algorithm or the "Tortoise and Hare" technique.

Step-by-Step Explanation:

1. Initialize Pointers

• slow and fast pointers are both set to the head of the linked list.

• slow will move one step at a time, while fast moves two steps at a time. This difference in speed helps identify cycles if they exist.

2. Loop Condition

The while loop continues as long as both fast and fast.next are not None.

• This condition ensures that fast can always move two nodes ahead without exceeding the list boundaries.

3. Move Pointers

Within the loop:

• slow advances by one node (slow = slow.next).

• fast advances by two nodes (fast = fast.next.next).

If there is a cycle, fast will eventually catch up to slow (they will point to the same node at some point). This is because fast moves through the list twice as quickly as slow, and a cycle would cause them to repeatedly traverse the same nodes.

4. Check for Cycle

If slow and fast meet at the same node (slow == fast), a cycle exists, and the method returns True.

• If fast reaches the end of the list (None), there is no cycle, and the method returns False.

Example

Suppose the linked list is: 3 -> 2 -> 0 -> -4 -> 2 (where -4 points back to 2, creating a cycle).

1. Initial State: slow and fast both point to the first node with value 3.

2. First Loop: slow moves to 2, fast moves to 0.

3. Second Loop: slow moves to 0, fast moves to 2 (skipping 0 and landing at 2 due to its two-step movement).

4. Third Loop: slow moves to -4, fast moves to -4.

At this point, slow and fast meet at the same node (-4), indicating a cycle. The method returns True.

Note

Efficiency

The hasCycle method runs in O(n) time complexity, where n is the number of nodes in the linked list, as both slow and fast pointers traverse the list only once. The space complexity is O(1), making this approach highly efficient.