Skills for tackling LeetCode problems - Fast and Slow Pointers / Hare & Tortoise algorithm.
This approach is often used in finding cycle in LinkedList. If there is no cycle, slower pointer can never catch up the faster pointer. If at any stage both of these pointers meet, the LinkedList has a cycle in it. The distance between the faster and slower pointer when the faster pointer is approaching to the slower one can be reduce to TWO possibilities: 1 and 2:
- The faster is one step behind the slower pointer, they will meet in the next move.
- The faster is two steps behind the slower pointer, after the next move, they will have the same scenario as (1).
1. LinkedList Cycle
Given the head of a Singly LinkedList, write a function to determine if the LinkedList has a cycle in it or not.
# Time complexity O(N). Space complexity O(1).
# class Node:
# def __init__(self, value, next=None):
# self.value = value
# self.next = next
def has_cycle(head):
slow, fast = head, head
while fast is not None and fast.next is not None:
fast = fast.next.next
slow = slow.next
if slow == fast:
return True
return False
Similar problem: Given the head of a LinkedList with a cycle, find the length of the cycle.
# Time complexity O(N). Space complexity O(1).
# class Node:
# def __init__(self, value, next=None):
# self.value = value
# self.next = next
def find_cycle_length(head):
slow, fast = head, head
while fast is not None and fast.next is not None:
fast = fast.next.next
slow = slow.next
if slow == fast:
return calculate_length(slow)
return 0
def calculate_length(slow):
current = slow
length = 0
while True:
current = current.next
length += 1
if current == slow:
return length
return length
2. Start of LinkedList Cycle
Given the head of a Singly LinkedList that contains a cycle, write a function to find the starting node of the cycle.
# Time complexity O(N). Space complexity O(1).
# class Node:
# def __init__(self, value, next=None):
# self.value = value
# self.next = next
def find_cycle_start(head):
slow, fast = head, head
length = 0
while fast is not None and fast.next is not None:
fast = fast.next.next
slow = slow.next
if slow == fast:
length = calculate_length(slow)
break
return find_start(head, length)
def calculate_length(slow):
current = slow
length = 0
while True:
current = current.next
length += 1
if current == slow:
return length
return length
def find_start(head, length):
p1 = p2 = head
while length > 0:
p2 = p2.next
length -= 1
while p1 != p2:
p1 = p1.next
p2 = p2.next
return p1
3. Happy Number
Any number will be called a happy number if, after repeatedly replacing it with a number equal to the sum of the square of all of its digits, leads us to number ‘1’. All other numbers will never reach ‘1’. Instead, they will be stuck in a cycle of numbers which does not include ‘1’.
# We will always be in a cycle.
# Time complexity O(log N). For a number N, the digit number M is M = log (N + 1).
# Space complexity O(1).
def find_happy_number(num):
fast = slow = num
while True:
slow = square_sum(slow) # move one step
fast = square_sum(square_sum(fast)) # move two step
if slow == fast: break
# The fast and slow pointers meet at '1' if the number is a happy numbers
# The fast and slow pointers meet at other value if the number is not a happy numbers
return slow == 1
def square_sum(num): # calculate sum of squared digits
SUM = 0
while num > 0:
digit = num % 10
SUM += digit ** 2
num //= 10
return SUM
4. Middle of the LinkedList
Given the head of a Singly LinkedList, write a method to return the middle node of the LinkedList.
# Time complexity O(N). Space complexity O(1).
# class Node:
# def __init__(self, value, next=None):
# self.value = value
# self.next = next
def find_middle_of_linked_list(head):
slow = fast = head
# When the fast pointer reaches the end of the LinkedList, the slow pointer will be pointing at the middle node.
while (fast is not None) and (fast.next is not None):
slow = slow.next
fast = fast.next.next
return slow
