🚴‍♀️141. Linked List Cycle

Easy | Grind 75 | September 6 tuesday, 2022

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.

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.

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
block 0th node.

Example 3

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

SOLUTION

The solution to finding a cycle in a linked list is using Floyd’s Cycle Detection Algorithm.The idea is to have two pointers, one moving faster than the other. If there is a cycle in the linked list, the two pointers are bound to meet at some point. This is because the faster pointer will eventually catch up to the slower pointer if there is a cycle. There are proofs showing that this collision is guaranteed if a cycle exists. A basic intuition (read on medium) can be seen by considering two runners on a track. You have two runners on a track. Runner A runs twice as fast as runner B. If the track is not circular, the two runners will never meet. However, if the track is circular, runner A is bound to catch with up runner B.

For our code implementation, we will have a slow and fast pointer. The slow pointer will move one step at a time while the fast point moves two-step at a time. Every time we iterate over the linked list, we check if the slow and the fast pointer point to the same node. If not, we traverse the two pointers according to their speed. We repeat this until our fast pointer points to none (indicating the end of the linked list) or the fast and slow pointers point to the same node (indicating cycle detection). One thing to note is that every time we iterate the linked list, we need to check if fast.next exists. When there is a cycle, this isn't an issue. However, when there is no cycle if we do not check if node.next exists, we will run into the issue of trying to access the next point of a null value.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        slow, fast = head, head
        
        # there should atleast be two nodes to make a cycle
        while fast and fast.next: 
            
            # slow take one step forward
            slow = slow.next
            # fast takes two steps forward
            fast = fast.next.next
            if slow == fast: 
                return True
        
        # the loop will terminate only if there is no cycle
        return False

TIME AND SPACE COMPLEXITY

TIME: O(n) where n is the number of nodes/length of the linked list. Not entirely sure if the slow pointer will always at most loop m+1 (length of the cycle) before colliding with the fast pointer. I looked at a few examples and every time the slow pointer traverses the loop at most once before colliding. In that case, we iterate atmost n times. Therefore the runtime is O(n)

SPACE: O(1) space is constant here since we only use two variables.