#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/data-structures/linked-lists/fast-slow-pointer-technique

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/data-structures/linked-lists/fast-slow-pointer-technique

Repovive

Fast-Slow Pointer Technique - Linked Lists | Data Structures | Repovive

Repovive.

Data Structures19 sections · 729 units49h total

Open in Course

Fast-Slow Pointer Technique

Two pointers, different speeds

The fast-slow pointer technique (also called Floyd's algorithm) uses two pointers moving at different speeds.

slow = head
fast = head
while fast != null and fast.next != null:
    slow = slow.next
    fast = fast.next.next

When fast reaches the end, slow is at the middle. Why? Fast moves twice as fast, so it covers twice the distance in the same number of steps.

This technique solves three categories of problems:

$1.$ Finding the middle of a list

$2.$ Detecting cycles

$3.$ Finding the start of a cycle

All in $O(n)$ time and $O(1)$ space.