Linked List Cycle easy

Problem Statement

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 second node.

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 first node.

Example 3:

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

Steps

1. Fast and Slow Pointers: We use two pointers, a slow pointer and a fast pointer. The slow pointer moves one step at a time, while the fast pointer moves two steps at a time.

2. Cycle Detection: If there is a cycle, the fast pointer will eventually lap the slow pointer. This is because the fast pointer is gaining one node on the slow pointer with each iteration.

3. No Cycle: If there is no cycle, the fast pointer will reach the end of the list (fast becomes None).

Explanation

The algorithm relies on the fact that if a cycle exists, the fast pointer will inevitably catch up to the slow pointer. Imagine the slow pointer as a car traveling at a constant speed, and the fast pointer as a car traveling at twice the speed. If both cars are on a circular track, the faster car will always eventually overtake the slower car.

If there's no cycle, the fast pointer will simply reach the end of the list, indicating no cycle.

Code

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

def hasCycle(head):
    """
    :type head: ListNode
    :rtype: bool
    """
    slow = head
    fast = head
    while fast and fast.next:  #Check for null pointer exceptions
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True  # Cycle detected
    return False  # No cycle


#Example Usage
head = ListNode(3)
head.next = ListNode(2)
head.next.next = ListNode(0)
head.next.next.next = ListNode(-4)
head.next.next.next.next = head.next #Creating the cycle

print(hasCycle(head)) #Output: True


head2 = ListNode(1)
head2.next = ListNode(2)

print(hasCycle(head2)) #Output: False

Complexity

• Time Complexity: O(N), where N is the number of nodes in the linked list. In the worst case (no cycle), the fast pointer iterates through the entire list.
• Space Complexity: O(1). The algorithm uses only a constant amount of extra space for the slow and fast pointers.