{"id":4527,"date":"2024-10-21T10:36:51","date_gmt":"2024-10-21T10:36:51","guid":{"rendered":"https:\/\/algocademy.com\/blog\/fast-and-slow-pointers-a-powerful-technique-for-solving-linked-list-problems\/"},"modified":"2026-10-15T10:34:49","modified_gmt":"2026-10-15T10:34:49","slug":"fast-and-slow-pointers-a-powerful-technique-for-solving-linked-list-problems","status":"publish","type":"post","link":"https:\/\/algocademy.com\/blog\/fast-and-slow-pointers-a-powerful-technique-for-solving-linked-list-problems\/","title":{"rendered":"Fast and Slow Pointers: Solve Linked List Problems in One Pass"},"content":{"rendered":"

Fast and slow pointers means walking a linked list with two references at different speeds, usually one node per step for slow<\/code> and two for fast<\/code>. Because the gap between them changes in a predictable way, you can detect a cycle, find the middle, or find the nth node from the end in a single pass with O(1) extra memory. This is also called Floyd’s tortoise and hare algorithm.<\/p>\n

All the code below is Python and was run on the sample lists shown. The node class and a small helper to build lists are in the first block.<\/p>\n

The setup<\/h2>\n
class ListNode:\n    def __init__(self, val=0, next=None):\n        self.val = val\n        self.next = next\n\ndef build(values, cycle_to=None):\n    \"\"\"Build a list from values; if cycle_to is an index, link the tail back to that node.\"\"\"\n    dummy = tail = ListNode()\n    nodes = []\n    for v in values:\n        tail.next = ListNode(v)\n        tail = tail.next\n        nodes.append(tail)\n    if cycle_to is not None:\n        tail.next = nodes[cycle_to]\n    return dummy.next\n<\/code><\/pre>\n
Every problem below uses the same loop shape:<\/p>\n
slow = fast = head\nwhile fast and fast.next:\n    slow = slow.next\n    fast = fast.next.next\n<\/code><\/pre>\n
The condition fast and fast.next<\/code> is the part people get wrong. You need both checks, in this order, because fast.next.next<\/code> crashes if fast<\/code> is None<\/code> or fast.next<\/code> is None<\/code>. The loop ends when fast<\/code> falls off the end, and at that moment slow<\/code> is at the halfway point.<\/p>\n
1. Detect a cycle<\/h2>\n
If the list has no cycle, fast<\/code> reaches None<\/code> and the loop ends. If there is a cycle, both pointers end up inside it, and fast<\/code> gains exactly one node on slow<\/code> every step. A gap that closes by one each step cannot be jumped over, so they must land on the same node.<\/p>\n
def has_cycle(head):\n    slow = fast = head\n    while fast and fast.next:\n        slow = slow.next\n        fast = fast.next.next\n        if slow is fast:\n            return True\n    return False\n\nprint(has_cycle(build([1, 2, 3, 4, 5])))              # False\nprint(has_cycle(build([1, 2, 3, 4, 5], cycle_to=2)))  # True\n<\/code><\/pre>\n
Compare nodes with is<\/code>, not ==<\/code> on values: two different nodes can hold the same value. The alternative is a set of visited nodes, which is simpler to write but uses O(n) memory. Fast and slow pointers use O(1).<\/p>\n
2. Find where the cycle starts<\/h2>\n
This is the classic follow-up (“Linked List Cycle II”). Once the pointers meet, reset one of them to the head and move both one step at a time. They meet again at the first node of the cycle.<\/p>\n
def cycle_start(head):\n    slow = fast = head\n    while fast and fast.next:\n        slow = slow.next\n        fast = fast.next.next\n        if slow is fast:\n            slow = head\n            while slow is not fast:\n                slow = slow.next\n                fast = fast.next\n            return slow\n    return None\n\nstart = cycle_start(build([1, 2, 3, 4, 5], cycle_to=2))\nprint(start.val)                       # 3\nprint(cycle_start(build([1, 2, 3])))   # None\n<\/code><\/pre>\n
Why it works: let a<\/em> be the number of nodes before the cycle, c<\/em> the cycle length, and k<\/em> how far into the cycle the meeting point is. When they meet, slow<\/code> has taken a + k<\/em> steps and fast<\/code> has taken twice that. Both are at the same spot, so the extra distance a + k<\/em> is a whole number of laps: a + k = m\u00b7c<\/em>. Rearranged, a = m\u00b7c – k<\/em>, which says that walking a<\/em> more steps from the meeting point lands on the cycle start. A pointer from the head also needs a<\/em> steps to get there, so they arrive together.<\/p>\n
3. Find the middle node<\/h2>\n
When fast<\/code> has moved to the end, slow<\/code> has moved half as far.<\/p>\n
def middle(head):\n    slow = fast = head\n    while fast and fast.next:\n        slow = slow.next\n        fast = fast.next.next\n    return slow\n\nprint(middle(build([1, 2, 3, 4, 5])).val)     # 3\nprint(middle(build([1, 2, 3, 4, 5, 6])).val)  # 4\n<\/code><\/pre>\n
For an even-length list this returns the second of the two middle nodes. If a problem wants the first one (you need it to split a list in two, for instance), change the loop condition to while fast.next and fast.next.next<\/code>. Check which one your problem asks for and test with both an odd and an even list.<\/p>\n
4. Remove or find the nth node from the end<\/h2>\n
Here the pointers move at the same speed, but you give fast<\/code> a head start of n<\/em> nodes. When fast<\/code> reaches the last node, slow<\/code> is just before the node you want. Starting both at a dummy node before the head handles the case where the head itself is removed.<\/p>\n
def remove_nth_from_end(head, n):\n    dummy = ListNode(0, head)\n    fast = slow = dummy\n    for _ in range(n):\n        fast = fast.next\n    while fast.next:\n        fast = fast.next\n        slow = slow.next\n    slow.next = slow.next.next\n    return dummy.next\n\ndef to_list(head):\n    out = []\n    while head:\n        out.append(head.val)\n        head = head.next\n    return out\n\nprint(to_list(remove_nth_from_end(build([1, 2, 3, 4, 5]), 2)))  # [1, 2, 3, 5]\nprint(to_list(remove_nth_from_end(build([1, 2, 3, 4, 5]), 5)))  # [2, 3, 4, 5]\n<\/code><\/pre>\n
This code assumes n<\/em> is between 1 and the list length, as most versions of the problem guarantee. If it might not be, check while advancing fast<\/code>. You can practice this exact problem in the Remove Nth Node From End Of List lesson<\/a>.<\/p>\n
5. Check for a palindrome<\/h2>\n
A list cannot be indexed from both ends, so the trick is to find the middle, reverse the second half in place, and compare the halves.<\/p>\n
def is_palindrome(head):\n    if not head:\n        return True\n    slow = fast = head\n    while fast.next and fast.next.next:\n        slow = slow.next\n        fast = fast.next.next\n    # reverse everything after slow\n    prev, cur = None, slow.next\n    while cur:\n        cur.next, prev, cur = prev, cur, cur.next\n    left, right = head, prev\n    while right:\n        if left.val != right.val:\n            return False\n        left, right = left.next, right.next\n    return True\n\nprint(is_palindrome(build([1, 2, 3, 2, 1])))  # True\nprint(is_palindrome(build([1, 2, 2, 1])))     # True\nprint(is_palindrome(build([1, 2, 3])))        # False\n<\/code><\/pre>\n
This runs in O(n) time and O(1) space, but it modifies the list. In an interview, say so, and mention that you can reverse the second half again before returning if the caller needs the original list. Reversing a list is its own pattern; see in-place reversal of a linked list<\/a> or the Reverse Linked List lesson<\/a>.<\/p>\n
It is not only for linked lists<\/h2>\n
Any sequence that is produced by repeatedly applying a function can have a cycle, and Floyd’s method finds it without storing what it has seen. The standard example is “Happy Number”: repeatedly replace a number with the sum of the squares of its digits; it either reaches 1 or loops forever.<\/p>\n
def is_happy(n):\n    def step(x):\n        return sum(int(d) ** 2 for d in str(x))\n    slow, fast = n, step(n)\n    while fast != 1 and slow != fast:\n        slow = step(slow)\n        fast = step(step(fast))\n    return fast == 1\n\nprint(is_happy(19))  # True\nprint(is_happy(2))   # False\n<\/code><\/pre>\n
“Find the Duplicate Number” (an array of n+1 values in the range 1 to n, treated as next-pointers) uses the same idea, including the cycle-start step.<\/p>\n
Complexity<\/h2>\n\n\n\n\n\n\n\n\n\n
Problem<\/th>\nTime<\/th>\nExtra space<\/th>\n<\/tr>\n<\/thead>\n
Detect cycle<\/td>\nO(n)<\/td>\nO(1)<\/td>\n<\/tr>\n
Find cycle start<\/td>\nO(n)<\/td>\nO(1)<\/td>\n<\/tr>\n
Middle node<\/td>\nO(n)<\/td>\nO(1)<\/td>\n<\/tr>\n
Nth from end<\/td>\nO(n)<\/td>\nO(1)<\/td>\n<\/tr>\n
Palindrome check<\/td>\nO(n)<\/td>\nO(1)<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
The cycle case is O(n) because once slow<\/code> enters the cycle, fast<\/code> catches it in at most one lap of the cycle.<\/p>\n
Common mistakes<\/h2>\n