DSA: Fast and Slow pointers

Posted on Sep 10, 2024

This is a pattern that uses two pointers approach, however there’s a special thing about this pattern:

One pointer moves faster than the other.

The Fast and Slow pattern follows the Hare and Tortoise algorithm.

The algorithm is pretty useful when dealing with cyclic Linked lists or arrays. It actually proves that by moving the pointers in that way they will be at the same position at some point in time.

So, the algorithm excels on finding a cycle in a linked list:

Check if a linked list has a cycle

class Node:
  def __init__(self, value, next=None):
    self.value = value
    self.next = next


def hasCycle(head: Node) -> bool:
  """ Returns True or False whether a cycle is found in a linked list """
  # two pointers, fast (hare) and slow (tortoise):
  fast, slow = head, head

  while fast is not None and fast.next is not None:
    fast = fast.next.next  # two jumps
    slow = slow.next       # one small step

    # the algorithm proves both pointers will meet at some point
    if fast == slow:
      return True

  return False

Find mid point of a linked list

class Node:
  def __init__(self, value, next=None):
    self.value = value
    self.next = next


def findMiddle(head: Node) -> Node:
  """ Returns the mid point of a linked list """
  fast, slow = head, head

  # if no cycle, fast will be None at the time
  # slow reaches the mid point of the linked list
  while fast is not None and fast.next is not None:
    fast = fast.next.next
    slow = slow.next

  return slow

Determine which node starts the cycle in a linked list

class Node:
  def __init__(self, value, next=None):
    self.value = value
    self.next = next


def findCycleStart(head: Node) -> Node:
  """ Returns the Node that indicates the begin of the linked list cycle  """
  fast, slow = head, head

  while fast is not None and fast.next is not None:
    fast = fast.next.next
    slow = slow.next

    # cycle found
    if fast == slow:
      cycle_length = findCycleLength(slow)
      break

  return getCycleStart(head, cycle_length)


def findCycleLength(slow: Node) -> int:
  """ Returns the length of the linked list cycle """
  current = slow
  cycle_length = 0

  # since we are in a cycle, break when both pointers meet again
  while True:
    current = current.next
    cycle_length += 1

    if current == slow:
      break

  return cycle_length


def getCycleStart(head: Node, cycle_length: int) -> Node:
  """ Returns the Node that starts the cycle"""
  fast, slow = head, head

  # move fast pointer  `cycle_length` jumps and pointers will meet again
  while cycle_length > 0:
    fast = fast.next
    cycle_length -= 1

  # one step at a time
  while fast != slow:
    fast = fast.next
    slow = slow.next

  return slow