02. Fast and Slow Pointers#

Theory#

Description#

The Fast and Slow Pointer technique, also called the Tortoise and Hare algorithm, is a powerful method for efficiently solving problems in linked lists and cyclic structures.

How It Works#

The slow pointer moves one step at a time.
The fast pointer moves two steps at a time.

The difference in speeds allows the fast pointer to catch up with the slow pointer if there's a cycle or to identify the middle of a structure.

Key Insights#

Cycle Detection: If a cycle exists, the fast pointer will meet the slow pointer inside the cycle.
Middle Element: The slow pointer will be at the middle when the fast pointer reaches the end.
Pattern Matching: Helps detect patterns like palindromes by dividing the structure into two parts.

Benefits#

Time Efficient: Solves problems in O(n) time with a single traversal.
Space Efficient: Requires O(1) space, avoiding extra data structures.
Simple & Elegant: Reduces complex problems to simple solutions.

Problems at a glance#

LC	Problem
141	1. Linked List Cycle	↗
142	2. Linked List Cycle II	↗
202	3. Happy Number	↗
876	4. Middle of the Linked List	↗
234	5. Palindrome Linked List	↗
143	6. Reorder List	↗
457	7. Circular Array Loop	↗
19	8. Remove Nth Node From End of List	↗
287	9. Find the Duplicate Number	↗

Problems#

1. Linked List Cycle (Leetcode:141)#

Problem Statement

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.

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

Example 3:

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

Constraints:

The number of the nodes in the list is in the range [0, 10^4].
-10^5 <= Node.val <= 10^5
pos is -1 or a valid index in the linked-list.

Follow up:

Can you solve it using O(1) (i.e. constant) memory?

Code and Explanation

Approach 1 — Floyd's Cycle DetectionApproach 2 — Hash Set

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        slow, fast = head, head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                return True
        return False

Explanation:

Initialize pointers: Set both slow and fast to head.
Move at different speeds: Advance slow one node and fast two nodes per iteration. If there is a cycle, the fast pointer will eventually lap the slow pointer inside the loop.
Detect meeting: If slow == fast, a cycle exists — return True.
No cycle: If fast reaches the end (None), the list is acyclic — return False.

Time: O(n) | Space: O(1)

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        seen = set()
        while head:
            if head in seen:
                return True
            seen.add(head)
            head = head.next
        return False

Explanation:

Track visited nodes: Walk the list and add each node to a hash set.
Detect repeat: If we encounter a node already in the set, we've found a cycle.
End of list: If we reach None, there is no cycle.

Time: O(n) | Space: O(n) — uses extra memory but is easier to reason about.

2. Linked List Cycle II (Leetcode:142)#

Problem Statement

Given the head of a linked list, return the node where the cycle begins. If there is no cycle, return null.

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 (0-indexed). It is -1 if there is no cycle. Note that pos is not passed as a parameter.

Do not modify the linked list.

Example 1:

Input: head = [3,2,0,-4], pos = 1
Output: tail connects to node index 1
Explanation: There is a cycle in the linked list, where tail connects to the second node.

Example 2:

Input: head = [1,2], pos = 0
Output: tail connects to node index 0
Explanation: There is a cycle in the linked list, where tail connects to the first node.

Example 3:

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

Constraints:

The number of the nodes in the list is in the range [0, 10^4].
-10^5 <= Node.val <= 10^5
pos is -1 or a valid index in the linked-list.

Follow up:

Can you solve it using O(1) (i.e. constant) memory?

Code and Explanation

Approach 1 — Floyd's Cycle DetectionApproach 2 — Hash Set

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow, fast = head, head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                slow = head
                while slow != fast:
                    slow = slow.next
                    fast = fast.next
                return slow
        return None

Explanation:

Phase 1 — Find meeting point: Use Floyd's algorithm. When slow == fast, both pointers are inside the cycle.
Phase 2 — Find cycle start: Reset slow to head. Move both pointers one step at a time. They meet at the node where the cycle begins.
Why it works: Let a = distance from head to cycle start, b = distance from cycle start to meeting point, and c = cycle length. At meeting: slow traveled a + b, fast traveled a + b + nc. Since fast = 2 × slow: a + b = nc, so a = nc - b. Starting one pointer at head and one at the meeting point, both moving one step, they converge at the cycle start after a steps.

Time: O(n) | Space: O(1)

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        seen = set()
        while head:
            if head in seen:
                return head
            seen.add(head)
            head = head.next
        return None

Explanation:

Track visited nodes: Walk the list, storing each node in a hash set.
First repeat is the start: The first node we see twice is where the cycle begins.
No cycle: Return None if we reach the end.

Time: O(n) | Space: O(n)

3. Happy Number (Leetcode:202)#

Problem Statement

Write an algorithm to determine if a number n is happy.

A happy number is a number defined by the following process:

Starting with any positive integer, replace the number by the sum of the squares of its digits.
Repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1.
Those numbers for which this process ends in 1 are happy.

Return true if n is a happy number, and false if not.

Example 1:

Input: n = 19
Output: true
Explanation:
1² + 9² = 82
8² + 2² = 68
6² + 8² = 100
1² + 0² + 0² = 1

Example 2:

Input: n = 2
Output: false

Constraints:

1 <= n <= 2^31 - 1

Code and Explanation

Approach 1 — Floyd's Cycle DetectionApproach 2 — Hash Set

class Solution:
    def isHappy(self, n: int) -> bool:
        def getNext(num: int) -> int:
            total = 0
            while num:
                digit = num % 10
                total += digit * digit
                num //= 10
            return total

        slow, fast = n, getNext(n)
        while slow != fast:
            slow = getNext(slow)
            fast = getNext(getNext(fast))
        return slow == 1

Explanation:

Model as a linked list: Each number maps to the sum of squares of its digits — an implicit sequence that either reaches 1 or enters a cycle.
Apply Floyd's algorithm: Treat slow and fast as pointers in this sequence. If they meet at 1, the number is happy; if they meet at any other value, a non-1 cycle exists.
Helper getNext: Computes the next number in the sequence by summing squared digits.

Time: O(log n) per step, bounded iterations | Space: O(1)

class Solution:
    def isHappy(self, n: int) -> bool:
        seen = set()
        while n != 1 and n not in seen:
            seen.add(n)
            n = sum(int(d) ** 2 for d in str(n))
        return n == 1

Explanation:

Track seen values: Store each number in the sequence in a set.
Cycle detection: If we revisit a number, we're in a loop that doesn't include 1.
Success: If we reach 1, return True.

Time: O(log n) | Space: O(log n)

4. Middle of the Linked List (Leetcode:876)#

Problem Statement

Given the head of a singly linked list, return the middle node of the linked list.

If there are two middle nodes, return the second middle node.

Example 1:

Input: head = [1,2,3,4,5]
Output: [3,4,5]
Explanation: The middle node of the list is node 3.

Example 2:

Input: head = [1,2,3,4,5,6]
Output: [4,5,6]
Explanation: Since the list has two middle nodes with values 3 and 4, we return the second one.

Constraints:

The number of nodes in the list is in the range [1, 100].
1 <= Node.val <= 100

Code and Explanation

Approach 1 — Fast and Slow PointersApproach 2 — Two Pass (Count Nodes)

class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow = head
        fast = head

        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

        return slow

Explanation:

Initialize: Both pointers start at head.
Move at different speeds: slow advances one node, fast advances two nodes per iteration.
Stop condition: When fast can no longer move (reaches end or last node), slow is at the middle. For even-length lists, slow lands on the second middle node because fast stops when it reaches the last node, not past it.

Time: O(n) | Space: O(1)

class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        count = 0
        curr = head
        while curr:
            count += 1
            curr = curr.next

        mid = count // 2
        curr = head
        for _ in range(mid):
            curr = curr.next
        return curr

Explanation:

First pass: Count total nodes.
Second pass: Walk count // 2 steps from head to reach the middle (second middle for even length).
Tradeoff: Requires two traversals but no pointer speed trick.

Time: O(n) | Space: O(1)

5. Palindrome Linked List (Leetcode:234)#

Problem Statement

Given the head of a singly linked list, return true if it is a palindrome or false otherwise.

Example 1:

Input: head = [1,2,2,1]
Output: true

Example 2:

Input: head = [1,2]
Output: false

Constraints:

The number of nodes in the list is in the range [1, 105].
0 <= Node.val <= 9

Code and Explanation

Approach 1 — Fast/Slow + Reverse Second HalfApproach 2 — Array + Two Pointers

class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        slow, fast = head, head

        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

        prev, curr = None, slow

        while curr:
            nxt = curr.next
            curr.next = prev
            prev = curr
            curr = nxt

        first_half, reversed_half = head, prev

        while reversed_half:
            if first_half.val != reversed_half.val:
                return False
            first_half = first_half.next
            reversed_half = reversed_half.next

        return True

Explanation:

Find middle: Use fast/slow pointers. slow ends at the start of the second half.
Reverse second half: In-place reversal from slow to end.
Compare halves: Walk head (first half) and prev (reversed second half) in parallel, comparing values.
Why it works: A palindrome reads the same forward and backward; reversing the second half lets us compare both directions in O(n) time with O(1) extra space.

Time: O(n) | Space: O(1)

class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        vals = []
        while head:
            vals.append(head.val)
            head = head.next

        lo, hi = 0, len(vals) - 1
        while lo < hi:
            if vals[lo] != vals[hi]:
                return False
            lo += 1
            hi -= 1
        return True

Explanation:

Copy values: Store all node values in an array.
Two-pointer check: Compare elements from both ends moving inward — classic palindrome test.
Tradeoff: Simpler to implement but uses O(n) extra space.

Time: O(n) | Space: O(n)

6. Reorder List (Leetcode:143)#

Problem Statement

You are given the head of a singly linked-list. The list can be represented as:
L0 → L1 → ... → Ln - 1 → Ln

Reorder the list to be on the following form:
L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → ...

You may not modify the values in the list's nodes. Only nodes themselves may be changed.

Example 1:

Input: head = [1,2,3,4]
Output: [1,4,2,3]

Example 2:

Input: head = [1,2,3,4,5]
Output: [1,5,2,4,3]

Constraints:

The number of nodes in the list is in the range [1, 5 * 10^4].
1 <= Node.val <= 1000

Code and Explanation

Approach 1 — Find Middle, Reverse, MergeApproach 2 — Stack-Assisted Merge

class Solution:
    def reorderList(self, head: Optional[ListNode]) -> None:
        if not head or not head.next:
            return

        slow, fast = head, head
        while fast.next and fast.next.next:
            slow = slow.next
            fast = fast.next.next

        second = slow.next
        slow.next = None

        prev, curr = None, second
        while curr:
            nxt = curr.next
            curr.next = prev
            prev = curr
            curr = nxt
        second = prev

        first = head
        while second:
            tmp1, tmp2 = first.next, second.next
            first.next = second
            second.next = tmp1
            first = tmp1
            second = tmp2

Explanation:

Find middle: Fast/slow pointers. Stop slow at the last node of the first half (fast.next.next guard prevents slow from entering second half).
Split: Break the list at slow.next and set slow.next = None.
Reverse second half: Standard in-place reversal.
Merge alternately: Interleave nodes from first half and reversed second half: first → second → first.next → second.next → ...

Time: O(n) | Space: O(1)

class Solution:
    def reorderList(self, head: Optional[ListNode]) -> None:
        if not head or not head.next:
            return

        slow, fast = head, head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

        stack = []
        curr = slow.next
        slow.next = None
        while curr:
            stack.append(curr)
            curr = curr.next

        first = head
        while stack:
            node = stack.pop()
            tmp = first.next
            first.next = node
            node.next = tmp
            first = tmp

Explanation:

Find middle: Same fast/slow technique to split the list.
Push second half onto stack: Stack gives LIFO access — nodes come out in reverse order.
Merge alternately: Pop from stack and weave into the first half.
Tradeoff: Uses O(n) stack space but avoids manual reversal logic.

Time: O(n) | Space: O(n)

7. Circular Array Loop (Leetcode:457)#

Problem Statement

You are playing a game involving a circular array of non-zero integers nums. Each nums[i] denotes the number of indices forward/backward you must move if you are located at index i:

If nums[i] is positive, move nums[i] steps forward, and
If nums[i] is negative, move nums[i] steps backward.

Since the array is circular, you may assume that moving forward from the last element puts you on the first element, and moving backwards from the first element puts you on the last element.

A cycle in the array consists of a sequence of indices seq of length k where:

Following the movement rules above results in the repeating index sequence
seq[0] -> seq[1] -> ... -> seq[k - 1] -> seq[0] -> ...
Every nums[seq[j]] is either all positive or all negative.
k > 1

Return true if there is a cycle in nums, or false otherwise.

Example 1:

Input: nums = [2,-1,1,2,2]
Output: true
Explanation: The graph shows how the indices are connected. White nodes are jumping forward, while red is jumping backward.
We can see the cycle 0 --> 2 --> 3 --> 0 --> ..., and all of its nodes are white (jumping in the same direction).

Example 2:

Input: nums = [-1,-2,-3,-4,-5,6]
Output: false
Explanation: The graph shows how the indices are connected. White nodes are jumping forward, while red is jumping backward.
The only cycle is of size 1, so we return false.

Example 3:

Input: nums = [1,-1,5,1,4]
Output: true
Explanation: The graph shows how the indices are connected. White nodes are jumping forward, while red is jumping backward.
We can see the cycle 0 --> 1 --> 0 --> ..., and while it is of size > 1, it has a node jumping forward and a node jumping backward, so it is not a cycle.
We can see the cycle 3 --> 4 --> 3 --> ..., and all of its nodes are white (jumping in the same direction).

Constraints:

1 <= nums.length <= 5000
-1000 <= nums[i] <= 1000
nums[i] != 0

Code and Explanation

Approach 1 — Floyd's Cycle DetectionApproach 2 — Visited Set

class Solution:
    def circularArrayLoop(self, nums: List[int]) -> bool:
        n = len(nums)

        def next_index(i: int) -> int:
            return (i + nums[i]) % n

        for i in range(n):
            if nums[i] == 0:
                continue

            slow, fast = i, i
            direction = nums[i] > 0

            while True:
                slow = next_index(slow)
                if nums[slow] * (1 if direction else -1) <= 0:
                    break

                fast = next_index(fast)
                if nums[fast] * (1 if direction else -1) <= 0:
                    break
                fast = next_index(fast)
                if nums[fast] * (1 if direction else -1) <= 0:
                    break

                if slow == fast:
                    if slow == next_index(slow):
                        break
                    return True

        return False

Explanation:

Treat indices as nodes: Each index i points to (i + nums[i]) % n, forming an implicit linked list on a circular array.
Direction constraint: A valid cycle requires all nodes to move in the same direction (all positive or all negative). Break if direction flips.
Floyd's detection: For each unvisited start index, run slow/fast. If they meet and cycle length > 1 (slow != next_index(slow)), return True.
Self-loop rejection: A cycle of size 1 (pointing to itself) is invalid per the problem.

Time: O(n²) worst case | Space: O(1)

class Solution:
    def circularArrayLoop(self, nums: List[int]) -> bool:
        n = len(nums)

        def next_index(i: int) -> int:
            return (i + nums[i]) % n

        for start in range(n):
            visited = set()
            i = start
            direction = nums[start] > 0

            while i not in visited:
                if nums[i] * (1 if direction else -1) <= 0:
                    break
                visited.add(i)
                nxt = next_index(i)
                if nxt == i:
                    break
                if nxt in visited:
                    return True
                i = nxt

        return False

Explanation:

Try each start index: For each index, follow the jump sequence.
Track visited indices: If we revisit an index within the same walk, a cycle of length > 1 exists (after direction and self-loop checks).
Direction check: Abort if any jump reverses direction.
Tradeoff: Uses O(n) space per attempt but is straightforward.

Time: O(n²) | Space: O(n)

8. Remove Nth Node From End of List (Leetcode:19)#

Problem Statement

Given the head of a linked list, remove the nth node from the end of the list and return its head.

Example 1:

Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]

Example 2:

Input: head = [1], n = 1
Output: []

Example 3:

Input: head = [1,2], n = 1
Output: [1]

Constraints:

The number of nodes in the list is sz.1 <= sz <= 300 <= Node.val <= 1001 <= n <= sz`

**Follow up: ** Could you do this in one pass?

Code and Explanation

Approach 1 — Two Pointers (n-Gap)Approach 2 — Two Pass (Count Length)

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        dummy = ListNode(0, head)
        slow = fast = dummy

        for _ in range(n + 1):
            fast = fast.next

        while fast:
            slow = slow.next
            fast = fast.next

        slow.next = slow.next.next
        return dummy.next

Explanation:

Dummy node: Handles edge case where the head itself is removed.
Create gap: Advance fast n + 1 steps ahead of slow so slow stops at the node before the one to delete.
Move together: When fast reaches the end, slow.next is the nth-from-end node — skip it.
One pass: Both pointers traverse the list exactly once.

Time: O(n) | Space: O(1)

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        length = 0
        curr = head
        while curr:
            length += 1
            curr = curr.next

        dummy = ListNode(0, head)
        curr = dummy
        for _ in range(length - n):
            curr = curr.next

        curr.next = curr.next.next
        return dummy.next

Explanation:

First pass: Count total nodes.
Second pass: Walk to the (length - n)-th node from the dummy and remove the next node.
Tradeoff: Two traversals but no gap-pointer trick needed.

Time: O(n) | Space: O(1)

9. Find the Duplicate Number (Leetcode:287)#

Problem Statement

Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.

There is only one repeated number in nums, return this repeated number.

You must solve the problem without modifying the array nums and using only constant extra space.

Example 1:

Input: nums = [1,3,4,2,2]
Output: 2

Example 2:

Input: nums = [3,1,3,4,2]
Output: 3

Example 3:

Input: nums = [3,3,3,3,3]
Output: 3

Constraints:

1 <= n <= 105
nums.length == n + 1
1 <= nums[i] <= n
All the integers in nums appear only once except for precisely one integer which appears two or more times.

Follow up:

How can we prove that at least one duplicate number must exist in nums?
Can you solve the problem in linear runtime complexity?

Code and Explanation

Approach 1 — Floyd's Cycle DetectionApproach 2 — Binary Search on Value Range

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        slow, fast = nums[0], nums[0]

        while True:
            slow = nums[slow]
            fast = nums[nums[fast]]
            if slow == fast:
                break

        slow = nums[0]
        while slow != fast:
            slow = nums[slow]
            fast = nums[fast]

        return slow

Explanation:

Model as linked list: Treat index i as a node pointing to nums[i]. With n + 1 values in range [1, n], the pigeonhole principle guarantees a duplicate, which creates a cycle.
Phase 1: Find meeting point inside the cycle using slow/fast pointers (move to nums[slow] and nums[nums[fast]]).
Phase 2: Reset one pointer to nums[0], move both one step at a time — they meet at the duplicate (cycle entrance).
Constraints satisfied: No array modification, O(1) extra space.

Time: O(n) | Space: O(1)

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        lo, hi = 1, len(nums) - 1

        while lo < hi:
            mid = (lo + hi) // 2
            count = sum(1 for x in nums if x <= mid)
            if count > mid:
                hi = mid
            else:
                lo = mid + 1

        return lo

Explanation:

Search space: The duplicate lies in [1, n].
Count ≤ mid: For each mid, count how many array values are ≤ mid. If count > mid, the duplicate is in the lower half (pigeonhole principle).
Narrow range: Binary search until lo == hi — that's the duplicate.
Tradeoff: O(n log n) time but intuitive and doesn't rely on cycle math. Does not modify the array.

Time: O(n log n) | Space: O(1)