Fast & Slow Pointers

Problem: nums has n + 1 integers, each in 1..n. Exactly one value repeats (possibly many times). Find it without modifying the array and with O(1) extra space.

Solve it on LeetCode ↗

Constraints: 1 ≤ n ≤ 10⁵ · 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.

From brute force to the pattern: A set of seen values is O(n) space; sorting modifies the array; checking every pair is O(n²). Following i → nums[i] turns the array into a linked list with a cycle whose entrance is the duplicate, which Floyd finds in O(n) time and O(1) space without changing anything.

Spot it: values are valid indices, so treat i → nums[i] as a "next" pointer. Index 0 is never a target (values ≥ 1), so it's the head of a tail. Two indices point at the duplicate value, so that node has two arrows coming in: the entrance of a cycle. "Duplicate + O(1) space + read-only" means Floyd.

Key insight: the duplicate is the cycle start. Run template C with slow = nums[slow] and fast = nums[nums[fast]].

Approach:

1. Treat each index i as a node whose next is nums[i], starting from index 0.
2. Phase 1: slow = nums[slow], fast = nums[nums[fast]] until they're equal.
3. Phase 2: reset slow to the start (nums[0]) and keep fast at the meeting point.
4. Move both one hop at a time. Where they meet is the cycle entrance, which is the duplicate.

from typing import List

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        # Treat every index as a "node" and nums[index] as its "next" arrow.
        # Index 0 is the head (no value is 0, so nothing points back at it).
        # One hop from index 0 lands on nums[0]; both runners start there.
        slow = nums[0]
        fast = nums[0]

        # Phase 1: slow hops once, fast hops twice, until they land together.
        while True:
            slow = nums[slow]          # slow: 1 hop
            fast = nums[fast]          # fast: first hop
            fast = nums[fast]          # fast: second hop (same as nums[nums[fast]])
            if slow == fast:
                break                  # they met somewhere inside the loop

        # Phase 2: put slow back at the start, leave fast at the meeting point.
        slow = nums[0]
        # Both now hop ONE step at a time; they meet at the loop entrance.
        while slow != fast:
            slow = nums[slow]
            fast = nums[fast]

        # Two different indices point at the entrance, so it is the duplicate.
        return slow

What the code is doing, line by line:

1. slow = nums[0] and fast = nums[0]: index 0 is the "head" of our hidden linked list (no value is 0, so no arrow ever points back to index 0). Its arrow leads to nums[0], so both runners start there.
2. while True: we don't know how many rounds phase 1 needs, so we loop "forever" and leave with break.
3. Inside the loop, slow = nums[slow] follows one arrow. fast = nums[fast] written twice follows two arrows. That is the same as nums[nums[fast]], split into two easy lines.
4. if slow == fast: break: they are on the same index, so they met inside the loop. We compare after moving because they start out equal.
5. Phase 2: slow = nums[0] sends slow back to the start while fast stays at the meeting point. while slow != fast: moves both one arrow at a time.
6. return slow: where they meet is the entrance of the loop. Two different indices point to it, so that value appears twice: it is the duplicate.

Dry run on the example: nums = [1, 3, 4, 2, 2] (expected answer 2). The arrows are 0→1, 1→3, 2→4, 3→2, 4→2.

The function returns 2.

Edge cases to test:

• The duplicate appears many times, e.g. [2, 2, 2, 2].
• The smallest case, [1, 1].
• The duplicate is at index 0.

Complexity: O(n) time, O(1) space.

Problem: Return the node where the cycle begins, or None if the list has no cycle. Don't modify the list.

Solve it on LeetCode ↗

Constraints: The number of the nodes in the list is in the range [0, 10⁴]. · -10⁵ ≤ Node.val ≤ 10⁵ · pos is -1 or a valid index in the linked-list.

From brute force to the pattern: A set of visited nodes returns the first repeat in O(n) time but O(n) space. Floyd's algorithm gets the entrance with two pointers: the distance from the head to the entrance equals the distance from the meeting point to it (modulo the loop length): O(1) space.

Spot it: "where the cycle begins" + linked list. It's template C exactly; the second visualizer above traces it.

Key insight: distance from head to entrance = distance from meeting point to entrance (mod the loop length).

Approach:

1. Run Floyd: slow 1 step, fast 2 steps, until they meet or fast falls off (no cycle → None).
2. Reset slow to head.
3. Move slow and fast one step each until they're the same node.
4. Return that node: the cycle's entrance.

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # Both runners start at the head of the list.
        slow = head
        fast = head

        # Phase 1: slow moves 1 step, fast moves 2 steps, until they meet
        # or fast runs off the end of the list.
        while fast is not None and fast.next is not None:
            slow = slow.next
            fast = fast.next.next
            if slow is fast:
                # Same NODE: fast lapped slow, so the list has a cycle.
                # Phase 2: send slow back to the head, keep fast where they met.
                slow = head
                # Move both ONE step at a time; they meet at the entrance.
                while slow is not fast:
                    slow = slow.next
                    fast = fast.next
                return slow

        # fast reached the end of the list, so there is no cycle.
        return None

What the code is doing, line by line:

1. slow = head, fast = head: both runners start at the head.
2. while fast is not None and fast.next is not None: keep going only while the hare can take two steps. If it can't, the list has an end, so there is no cycle.
3. slow = slow.next (1 step) and fast = fast.next.next (2 steps).
4. if slow is fast: both point at the same node object, so the hare has lapped the tortoise: there is a cycle.
5. Phase 2: slow = head moves one runner back to the head; fast stays at the meeting point. The math in section 2 says both are now the same distance from the entrance.
6. while slow is not fast: move both one step at a time. When they become the same node, return slow returns the entrance.
7. return None after the outer loop: the hare fell off the end, so there is no cycle.

Dry run on the example: LeetCode example 1, head = [3, 2, 0, -4], pos = 1 (the tail -4 points back to the node 2). Node values are shown.

The function returns the node with value 2 (index 1).

Edge cases to test:

• No cycle → None.
• The cycle starts at the head.
• A single node pointing to itself.

Complexity: O(n) time, O(1) space.

Problem: Rearrange L0 → L1 → … → Ln into L0 → Ln → L1 → Ln−1 → … in place.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: The number of nodes in the list is in the range [1, 5 * 10⁴]. · 1 ≤ Node.val ≤ 1000

From brute force to the pattern: Copying the nodes into an array and re-linking with two indices is O(n) time but O(n) space. Middle + reverse + merge does it in place in O(n) time and O(1) space.

Spot it: you need the back half in reverse order. That's (1) find the middle with fast/slow, (2) reverse the second half (pattern 05), (3) weave.

Key insight: stop slow at the end of the first half (while fast.next and fast.next.next) so you can cut slow.next = None.

Approach:

1. Find the end of the first half with fast/slow (loop while fast.next and fast.next.next).
2. Cut the list after slow and reverse the second half.
3. Weave: one node from the first half, then one from the reversed second half, and so on.
4. The first half is equal or one longer, so stop when the second half runs out.

class Solution:
    def reorderList(self, head: Optional[ListNode]) -> None:
        # A list with 0 or 1 nodes is already in the right order.
        if head is None or head.next is None:
            return

        # Step 1: find the END of the first half.
        # Looking at fast.next and fast.next.next makes slow stop one node
        # earlier than usual: on the last node of the first half.
        slow = head
        fast = head
        while fast.next is not None and fast.next.next is not None:
            slow = slow.next
            fast = fast.next.next

        # Step 2: cut the list after slow ...
        second_half = slow.next
        slow.next = None                          # the first half now ends at slow
        # ... and reverse the second half (pattern 05).
        previous_node = None
        current_node = second_half
        while current_node is not None:
            next_node = current_node.next         # remember the rest of the list
            current_node.next = previous_node     # flip this node's arrow backwards
            previous_node = current_node          # previous moves forward
            current_node = next_node              # current moves forward
        # previous_node is now the first node of the reversed second half.

        # Step 3: weave: one node from the first half, then one from the second.
        first = head
        second = previous_node
        while second is not None:
            first_next = first.next               # save the rest of the first half
            second_next = second.next             # save the rest of the second half
            first.next = second                   # first node points to second node
            second.next = first_next              # second node points to the next first-half node
            first = first_next                    # step forward in the first half
            second = second_next                  # step forward in the second half

What the code is doing, line by line:

1. if head is None or head.next is None: return: an empty list or a single node is already in the right order.
2. Step 1, find the end of the first half. Both runners start at head. The loop condition fast.next is not None and fast.next.next is not None looks one node further ahead than the usual check, so slow stops on the last node of the first half (the first middle).
3. Step 2, cut. second_half = slow.next remembers where the second half begins. slow.next = None ends the first half there, so now we have two separate lists.
4. Step 2, reverse the second half. previous_node starts as None and current_node at the start of the second half. Each loop round: save next_node = current_node.next (or we'd lose the rest of the list), flip the arrow with current_node.next = previous_node, then move both names one node forward. When current_node becomes None, previous_node is the head of the reversed half.
5. Step 3, weave. first walks the first half and second walks the reversed second half. Each round we save both "next" nodes first, then link first → second → first_next, and step both names forward.
6. The loop stops when second runs out. The first half is the same length or one node longer, and its last node already ends with None because of the cut.

Dry run on the example: LeetCode example 2, head = [1, 2, 3, 4, 5] (expected [1, 5, 2, 4, 3]).

Final list: 1 → 5 → 2 → 4 → 3.

Edge cases to test:

• One or two nodes → unchanged.
• Odd length: the middle node ends up last.
• Forgetting to cut the first half off (set its tail's next to None) creates a cycle.

Complexity: O(n) time, O(1) space.

Problem: From index i you jump nums[i] steps (wrapping around). Is there a cycle of length > 1 where every jump goes the same direction?

Solve it on LeetCode ↗

Constraints: 1 ≤ nums.length ≤ 5000 · -1000 ≤ nums[i] ≤ 1000 · nums[i] != 0

From brute force to the pattern: Simulating from every start with a visited set is O(n²). Fast/slow pointers detect a loop from a start in O(n) with O(1) space, and marking failed paths as 0 keeps the total at O(n).

Spot it: "circular" + "jump by nums[i]" defines a next function (i + nums[i]) % n. Detect a cycle with fast/slow, with extra rules.

Key insight: abort a run as soon as fast would step onto a node of the opposite direction or a self-loop (next(j) == j). Afterwards, zero out the path you walked so each index is explored once overall: O(n).

Approach:

1. For each unvisited start i, remember its direction (forward if nums[i] > 0).
2. Run slow/fast with next(i) = (i + nums[i]) % n, but only while fast's next two steps keep that direction and aren't self-loops.
3. If slow == fast, a valid cycle exists → True.
4. Otherwise zero out every index on this same-direction path so it's never explored again.
5. If no start finds a cycle, return False.

class Solution:
    def next_index(self, nums: List[int], index: int) -> int:
        # Jump nums[index] steps. "% size" wraps around the circle;
        # in Python the result of % is always between 0 and size - 1,
        # even when the jump is negative.
        size = len(nums)
        return (index + nums[index]) % size

    def is_legal_step(self, nums: List[int], index: int, forward: bool) -> bool:
        # 1) 0 means "already explored, leads nowhere": not legal.
        if nums[index] == 0:
            return False
        # 2) It must move in the same direction as the run we started.
        moves_forward = nums[index] > 0
        if moves_forward != forward:
            return False
        # 3) Jumping back onto itself is a loop of length 1: not allowed.
        if self.next_index(nums, index) == index:
            return False
        return True

    def circularArrayLoop(self, nums: List[int]) -> bool:
        size = len(nums)
        for start in range(size):
            # Skip positions an earlier run already proved useless.
            if nums[start] == 0:
                continue
            # Remember this run's direction (True = forward, False = backward).
            forward = nums[start] > 0

            # Floyd: slow makes 1 jump per round, fast makes 2 jumps.
            slow = start
            fast = start
            while True:
                # fast may only jump if its current spot is legal ...
                if not self.is_legal_step(nums, fast, forward):
                    break
                fast_after_one_jump = self.next_index(nums, fast)
                # ... and the spot after its first jump is legal too.
                if not self.is_legal_step(nums, fast_after_one_jump, forward):
                    break
                slow = self.next_index(nums, slow)
                fast = self.next_index(nums, fast_after_one_jump)
                if slow == fast:
                    return True                   # met inside a valid loop

            # No loop from this start. Zero out the same-direction path we walked
            # so that no later start walks it again (this keeps the total O(n)).
            index = start
            while nums[index] != 0:
                moves_forward = nums[index] > 0
                if moves_forward != forward:
                    break                         # the path turned around: stop
                following = self.next_index(nums, index)   # compute BEFORE zeroing
                nums[index] = 0
                index = following
        return False

What the code is doing, line by line:

1. next_index(nums, index) is the "next pointer": jump nums[index] steps and wrap around with % size. In Python, % always gives a number from 0 to size - 1, even for negative jumps (for example -1 % 5 is 4).
2. is_legal_step(nums, index, forward) answers "may a valid loop pass through this index?" in three checks: it is not already zeroed out, it moves in the same direction as this run (moves_forward != forward means it would turn around), and it does not jump onto itself (a loop of length 1 is not allowed).
3. The main for start in range(size): tries every index as a starting point and skips indices that are already 0. forward = nums[start] > 0 records this run's direction.
4. The while True: loop is Floyd's race with extra rules. Before fast jumps, both the spot it stands on and the spot after its first jump must be legal. If either isn't, break ends this run. Otherwise slow makes one jump, fast makes two (fast_after_one_jump, then one more), and if slow == fast: return True, because only legal steps were taken, so this is a valid loop.
5. If the run ended without a meeting, the second while loop walks the same path again and sets each same-direction index to 0. We compute following before zeroing, because next_index needs the old value. Zeroing means "dead end, never explore again", which keeps the total work O(n).
6. If no start finds a loop, return False.

Dry run on the example: LeetCode example 1, nums = [2, -1, 1, 2, 2] (expected True: the loop 0 → 2 → 3 → 0 only moves forward).

The function returns True.

Edge cases to test:

• A self-loop (nums[i] % n == 0) doesn't count.
• A loop that mixes forward and backward moves doesn't count.
• Large jumps, so take % n (and handle negatives).

Complexity: O(n) time, O(1) space (it modifies the input as a visited marker).

Problem: Does the linked list contain a cycle?

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: The number of the nodes in the list is in the range [0, 10⁴]. · -10⁵ ≤ Node.val ≤ 10⁵ · pos is -1 or a valid index in the linked-list.

From brute force to the pattern: Storing every visited node in a set detects a repeat in O(n) time but O(n) space. Two pointers at different speeds detect the cycle with O(1) space.

Spot it: the warm-up. Template B; the follow-up "O(1) memory" rules out the visited-set solution.

Approach:

1. Start both runners at the head: slow = head and fast = head.
2. While fast and fast.next exist: slow takes 1 step, fast takes 2.
3. If they become the same node, there's a cycle.
4. If fast falls off the end, there isn't.

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        # Both runners start at the head.
        slow = head
        fast = head
        # fast needs two valid nodes ahead of it to take its 2 steps.
        while fast is not None and fast.next is not None:
            slow = slow.next                      # 1 step
            fast = fast.next.next                 # 2 steps
            if slow is fast:
                return True                       # same NODE: fast lapped slow
        return False                              # fast reached the end: no loop

What the code is doing, line by line:

1. slow = head, fast = head: both runners start at the head.
2. while fast is not None and fast.next is not None: continue only while the hare has two nodes in front of it. An empty list makes this false right away.
3. slow = slow.next takes 1 step; fast = fast.next.next takes 2 steps.
4. if slow is fast: return True: checked after moving (at the start they are trivially equal). Being on the same node means the hare came around the loop and caught up.
5. return False: the loop ended because the hare reached the end of the list, and a list with an end has no cycle.

Dry run on the example: LeetCode example 1, head = [3, 2, 0, -4], pos = 1 (the tail points back to the node 2).

The function returns True.

Edge cases to test:

• An empty list → False.
• A single node with no cycle.
• A cycle back to the head.

Complexity: O(n) time, O(1) space.

Problem: Return the middle node of a linked list (the second middle when the length is even).

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: The number of nodes in the list is in the range [1, 100]. · 1 ≤ Node.val ≤ 100

From brute force to the pattern: Counting the length and then walking n / 2 steps is two passes; copying into an array uses O(n) space. Fast/slow finds the middle in one pass with O(1) space.

Spot it: "Middle" + singly linked list → template A.

Approach:

1. Start both runners at the head: slow = head and fast = head.
2. While fast and fast.next: slow takes 1 step, fast takes 2.
3. Return slow.

class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # Both runners start at the head.
        slow = head
        fast = head
        # Keep going while fast can still take 2 steps.
        while fast is not None and fast.next is not None:
            slow = slow.next                      # 1 step
            fast = fast.next.next                 # 2 steps
        # fast is at (or just past) the end, so slow is in the middle.
        # For an even length this is the SECOND of the two middle nodes.
        return slow

What the code is doing, line by line:

1. slow = head, fast = head: both runners start at the head.
2. while fast is not None and fast.next is not None: keep going while the hare can take two steps.
3. slow = slow.next (1 step), fast = fast.next.next (2 steps).
4. return slow: the hare is at the last node (odd length) or just past it (None, even length). Having walked half as far, the tortoise is in the middle. For an even length that is the second of the two middle nodes, which is what LeetCode wants.

Dry run on the example: LeetCode example 2, head = [1, 2, 3, 4, 5, 6] (expected the node 4).

The function returns the node 4 (so the answer list is [4, 5, 6]).

Edge cases to test:

• Even length → return the second middle.
• A single node.
• Two nodes → the second.

Complexity: O(n) time, O(1) space.

Problem: Keep replacing n with the sum of the squares of its digits. If you reach 1, n is happy; otherwise the numbers loop forever. Is n happy?

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: 1 ≤ n ≤ 2³¹ - 1

From brute force to the pattern: Following the sequence while storing seen numbers in a set works (O(log n) steps per number) but uses memory. Treating "next = sum of digit squares" as a linked list lets Floyd's fast/slow detect the cycle in O(1) space.

Spot it: "Loops forever" + a well-defined next value → cycle detection on numbers instead of nodes.

Approach:

1. Define sum_of_digit_squares(x) = sum of the squared digits of x (the "next pointer").
2. slow = n, fast = sum_of_digit_squares(n).
3. Advance slow by 1 and fast by 2 until fast == 1 or slow == fast.
4. Happy exactly when fast == 1.

class Solution:
    def sum_of_digit_squares(self, number: int) -> int:
        # This is the implicit "next pointer": 19 -> 1*1 + 9*9 = 82.
        total = 0
        while number > 0:
            digit = number % 10                   # the last digit
            total = total + digit * digit         # add its square
            number = number // 10                 # chop the last digit off
        return total

    def isHappy(self, n: int) -> bool:
        # slow starts at n; fast starts one step ahead so the loop can run.
        slow = n
        fast = self.sum_of_digit_squares(n)
        # Stop when fast reaches 1 (happy) or catches slow (stuck in a loop).
        while fast != 1 and slow != fast:
            slow = self.sum_of_digit_squares(slow)    # slow: 1 step
            fast = self.sum_of_digit_squares(fast)    # fast: first step
            fast = self.sum_of_digit_squares(fast)    # fast: second step
        # Happy exactly when the chain reached 1.
        return fast == 1

What the code is doing, line by line:

1. sum_of_digit_squares(number) is the "next pointer". number % 10 gives the last digit, we add its square to total, and number // 10 (whole-number division) chops that digit off. When number reaches 0, every digit has been used.
2. In isHappy, slow = n and fast = sum_of_digit_squares(n): fast starts one step ahead so that slow != fast is true and the loop can begin.
3. while fast != 1 and slow != fast: stop when fast reaches 1 (happy, and 1 maps to itself forever) or when fast catches slow (we are stuck in a loop that doesn't contain 1).
4. Inside: slow takes one step, fast takes two steps (two separate calls, one per line).
5. return fast == 1: True if we stopped because we reached 1, False if we stopped because the runners met.

Dry run on the example: LeetCode example 1, n = 19 (expected True). First, one call of the helper, sum_of_digit_squares(19):

The helper returns 82. Now the race in isHappy(19):

fast reached 1, so the function returns True.

Edge cases to test:

• n = 1 → True immediately.
• n = 7 → True (it takes a few steps).
• n = 2 → False (falls into the 4 → 16 → … loop).

Complexity: Each step is O(log n) digits, and the sequence quickly drops below a few hundred, so the time is effectively O(log n). O(1) space.

Problem: Delete the node at index ⌊n/2⌋ and return the head.

Solve it on LeetCode ↗

Constraints: The number of nodes in the list is in the range [1, 10⁵]. · 1 ≤ Node.val ≤ 10⁵

From brute force to the pattern: Counting the nodes and walking to n // 2 − 1 takes two passes. An offset fast/slow pair stops one node early in a single pass.

Spot it: To unlink a node you need the node before it. Use fast & slow, but give fast a one-round head start so slow stops one node early.

Approach:

1. If there's only one node, return None.
2. slow = head, fast = head.next.next (fast starts two steps ahead).
3. While fast and fast.next: slow takes 1 step, fast takes 2.
4. slow is now just before the middle: slow.next = slow.next.next.

class Solution:
    def deleteMiddle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # A single node IS the middle; deleting it leaves an empty list.
        if head.next is None:
            return None
        # Give fast a head start of one round (2 nodes).
        # Then slow stops on the node just BEFORE the middle.
        slow = head
        fast = head.next.next
        while fast is not None and fast.next is not None:
            slow = slow.next
            fast = fast.next.next
        # Unlink the middle: slow now points past it.
        middle = slow.next
        slow.next = middle.next
        return head

What the code is doing, line by line:

1. if head.next is None: return None: with a single node, that node is the middle; deleting it leaves an empty list.
2. slow = head, fast = head.next.next: fast gets a one-round head start (two nodes). That shifts where slow stops by one node, so slow ends on the node just before the middle, which is the node we need in order to unlink the middle. (head.next.next is safe: we know head.next exists; it may be None, which the loop handles.)
3. The usual loop: while fast is not None and fast.next is not None: slow 1 step, fast 2 steps.
4. middle = slow.next names the node to delete, and slow.next = middle.next makes the list skip over it.
5. return head: the head itself never changes (the list has at least 2 nodes here).

Dry run on the example: LeetCode example 1, head = [1, 3, 4, 7, 1, 2, 6] (n = 7, so delete index 3, the node 7). The value 1 appears twice, so each node also shows its position.

The function returns 1 → 3 → 4 → 1 → 2 → 6.

Edge cases to test:

• A single node → empty list.
• Two nodes → delete the second.
• Even length → delete node n // 2 (0-indexed).

Complexity: O(n) time, O(1) space.

Problem: Do the list's values read the same forwards and backwards? Follow-up: use O(1) extra space.

Solve it on LeetCode ↗

Constraints: The number of nodes in the list is in the range [1, 10⁵]. · 0 ≤ Node.val ≤ 9

From brute force to the pattern: An array copy or a stack gives O(n) space. Middle-finding plus an in-place reversal of the second half compares the halves with O(1) extra space (and you can reverse it back afterwards).

Spot it: You need to compare the first half with the second half read backwards → find the middle with fast/slow, then reverse half (pattern 05).

Approach:

1. Fast/slow: slow lands on the first node of the second half.
2. Reverse the list from slow onward.
3. Walk from head and from the reversed half together until the reversed half ends.
4. Any mismatch → False; otherwise True.

class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        # Step 1: slow walks to the first node of the second half.
        slow = head
        fast = head
        while fast is not None and fast.next is not None:
            slow = slow.next
            fast = fast.next.next

        # Step 2: reverse the list from slow to the end.
        previous_node = None
        current_node = slow
        while current_node is not None:
            next_node = current_node.next         # remember the rest
            current_node.next = previous_node     # flip the arrow
            previous_node = current_node          # move both forward
            current_node = next_node
        # previous_node is now the head of the reversed second half.

        # Step 3: compare the first half with the reversed second half.
        left = head
        right = previous_node
        while right is not None:                  # the second half is never longer
            if left.val != right.val:
                return False                      # a mismatch: not a palindrome
            left = left.next
            right = right.next
        return True

What the code is doing, line by line:

1. Step 1: the usual fast/slow loop (while fast is not None and fast.next is not None) leaves slow on the first node of the second half (the second middle).
2. Step 2: reverse the list from slow to the end. Each round saves next_node, flips current_node.next to point backwards, and moves previous_node and current_node one node forward. Afterwards previous_node is the head of the reversed second half.
3. Step 3: left starts at head and right at the reversed half. While right is not None, compare left.val with right.val. Any difference means return False; otherwise move both one node.
4. return True: every pair matched. We loop on right because the second half is never longer than the first.

Dry run on the example: LeetCode example 1, head = [1, 2, 2, 1] (expected True). Values repeat, so each node also shows its position.

The function returns True.

Edge cases to test:

• A single node → True.
• Even and odd lengths.
• Two nodes with different values → False.

Complexity: O(n) time, O(1) space. (It leaves the second half reversed; reverse it back if the caller cares.)

Problem: Sort a linked list in O(n log n) time.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: The number of nodes in the list is in the range [0, 5 * 10⁴]. · -10⁵ ≤ Node.val ≤ 10⁵

From brute force to the pattern: Copying values into an array and calling sort() uses O(n) space. Merge sort on the list itself is O(n log n) time with only the recursion stack; the split uses fast/slow pointers.

Spot it: Merge sort suits linked lists because it never needs random access; fast/slow finds the split point.

Approach:

1. Base case: 0 or 1 node is already sorted.
2. slow = head, fast = head.next; advance until fast ends. slow is now the end of the first half.
3. Cut after slow and sort both halves recursively.
4. Merge the two sorted halves (helper merge_two_sorted_lists) using a dummy node and a tail pointer.

class Solution:
    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # Base case: 0 or 1 node is already sorted.
        if head is None or head.next is None:
            return head

        # Find the END of the first half. fast starts one node ahead,
        # which makes slow stop on the last node of the first half.
        slow = head
        fast = head.next
        while fast is not None and fast.next is not None:
            slow = slow.next
            fast = fast.next.next

        # Cut the list into two halves.
        second_half = slow.next
        slow.next = None

        # Sort each half (recursion), then merge the two sorted halves.
        sorted_first = self.sortList(head)
        sorted_second = self.sortList(second_half)
        return self.merge_two_sorted_lists(sorted_first, sorted_second)

    def merge_two_sorted_lists(self, left: Optional[ListNode], right: Optional[ListNode]) -> Optional[ListNode]:
        # A dummy node in front means we never special-case the first node.
        dummy = ListNode()
        tail = dummy                              # tail = last node of the merged list
        while left is not None and right is not None:
            # Take the smaller front node and attach it after tail.
            if left.val <= right.val:
                tail.next = left
                left = left.next
            else:
                tail.next = right
                right = right.next
            tail = tail.next
        # One list ran out; attach whatever is left of the other one.
        if left is not None:
            tail.next = left
        else:
            tail.next = right
        return dummy.next

What the code is doing, line by line:

1. if head is None or head.next is None: return head: the base case. A list of 0 or 1 nodes is already sorted, and it is what stops the recursion.
2. slow = head, fast = head.next: fast starts one node ahead, so when the loop ends slow is on the last node of the first half. (If both started at head, a 2-node list would never shrink and the recursion would never end.)
3. second_half = slow.next then slow.next = None cuts the list into two separate halves.
4. sorted_first = self.sortList(head) and sorted_second = self.sortList(second_half): recursion. Trust that each call returns its half sorted.
5. merge_two_sorted_lists(left, right): a dummy node sits in front of the answer so the first real node needs no special case; tail is the last node of the merged list so far. Each round attaches the smaller of the two front nodes after tail and moves that list forward. (<= keeps equal values in their original order.)
6. When one list runs out, the if left is not None ... else ... attaches the rest of the other list in one go, because it is already sorted. return dummy.next skips the dummy.

Dry run on the example: LeetCode example 1, head = [4, 2, 1, 3] (expected [1, 2, 3, 4]). Each row is one event in the order it happens; depth 0 is the first call.

The function returns 1 → 2 → 3 → 4.

Edge cases to test:

• Empty or single-node list.
• Already sorted or reverse sorted.
• Duplicates and negative values.

Complexity: O(n log n) time, O(log n) recursion stack.

Problem: In a list of even length n, node i and node n−1−i are twins. Return the largest twin sum.

Solve it on LeetCode ↗

Constraints: The number of nodes in the list is an even integer in the range [2, 10⁵]. · 1 ≤ Node.val ≤ 10⁵

From brute force to the pattern: Copying values to an array and summing a[i] + a[n − 1 − i] is O(n) space. Middle + reverse + walk does it in place with O(1) space.

Spot it: Pair the first half with the second half read backwards → middle (fast/slow) + reverse the second half.

Approach:

1. Fast/slow: slow lands on the first node of the second half.
2. Reverse the second half.
3. Walk from head and from the reversed half together, adding twin values.
4. Return the maximum sum.

class Solution:
    def pairSum(self, head: Optional[ListNode]) -> int:
        # Step 1: slow walks to the first node of the second half.
        slow = head
        fast = head
        while fast is not None and fast.next is not None:
            slow = slow.next
            fast = fast.next.next

        # Step 2: reverse the second half.
        previous_node = None
        current_node = slow
        while current_node is not None:
            next_node = current_node.next         # remember the rest
            current_node.next = previous_node     # flip the arrow
            previous_node = current_node          # move both forward
            current_node = next_node

        # Step 3: left walks forward from the head, right walks forward through
        # the reversed half, which means "backwards" through the original list.
        best_sum = 0
        left = head
        right = previous_node
        while right is not None:
            twin_sum = left.val + right.val
            if twin_sum > best_sum:
                best_sum = twin_sum               # a new best pair
            left = left.next
            right = right.next
        return best_sum

What the code is doing, line by line:

1. Step 1: the usual fast/slow loop leaves slow on the first node of the second half (the length is even, so this is node n/2).
2. Step 2: reverse the second half with previous_node / current_node / next_node, exactly like in 234. previous_node ends on the old last node.
3. Step 3: left walks forward from the head while right walks the reversed half, which visits the original list from the back. So left and right are always twins.
4. twin_sum = left.val + right.val; if twin_sum > best_sum: best_sum = twin_sum keeps the largest sum seen so far (all values are positive, so starting from 0 is safe).
5. return best_sum once the reversed half is used up.

Dry run on the example: LeetCode example 1, head = [5, 4, 2, 1] (expected 6).

The function returns 6.

Edge cases to test:

• Two nodes → their sum.
• All equal values.
• The maximum pair is in the middle.

Complexity: O(n) time, O(1) space.

Problem: Remove the n-th node from the end of the linked list and return its head, in one pass.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: The number of nodes in the list is sz. · 1 ≤ sz ≤ 30 · 0 ≤ Node.val ≤ 100 · 1 ≤ n ≤ sz

From brute force to the pattern: Counting the length, then walking to position length − n, is two passes. A fixed gap between two pointers finds the node in one pass; the dummy node handles deleting the head.

Spot it: "N-th from the end" without knowing the length → two runners. Here they move at the same speed but with a head start of n, so when the leader falls off the end, the follower stands just before the target.

Key insight: A dummy node before head means the node before the target always exists, even when the target is the head itself (n equal to the length).

Approach:

1. Put a dummy node in front of head.
2. Move fast forward n nodes from head.
3. Start slow at dummy, then move both one step at a time until fast is None.
4. slow is now just before the node to delete: set slow.next = slow.next.next.
5. Return dummy.next (the head may have changed).

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        # a fake node before head, so removing the head needs no special case
        dummy = ListNode(0, head)
        fast = head
        # give fast a head start of n nodes
        for _ in range(n):
            fast = fast.next
        slow = dummy
        # move together; the gap between them stays n
        while fast is not None:
            fast = fast.next
            slow = slow.next
        # slow is right before the node to remove: skip over it
        slow.next = slow.next.next
        return dummy.next

What the code is doing, line by line:

1. dummy = ListNode(0, head): a placeholder whose next is the real head.
2. for _ in range(n): fast = fast.next: fast walks n nodes ahead. (_ means we don't need the loop counter.)
3. slow = dummy: slow starts one node before the head. That extra step is what leaves it in front of the target, not on it.
4. while fast is not None: move both one step per round; the gap of n + 1 positions between them never changes.
5. When fast is None (just past the last node), slow is n + 1 positions back: the node before the target.
6. slow.next = slow.next.next: unlink the target. return dummy.next handles the case where the old head was removed.

Dry run on the example:

head = [1, 2, 3, 4, 5], n = 2 (LeetCode Example 1). Returns [1, 2, 3, 5].

Edge cases to test:

• Remove the head (n equals the length).
• A single-node list → empty.
• Remove the last node (n = 1).

Complexity: O(L) time (one pass over the list), O(1) space.

Problem: Values are in 1..n and each appears once or twice. Return all values that appear twice, in O(n) time and O(1) extra space.

Solve it on LeetCode ↗

Constraints: n == nums.length · 1 ≤ n ≤ 10⁵ · 1 ≤ nums[i] ≤ n · Each element in nums appears once or twice.

From brute force to the pattern: A hash set finds duplicates in O(n) but uses O(n) space; sorting changes the order and costs O(n log n). Using the sign at each value's home index as a marker gives O(n) time with O(1) extra space.

Spot it: Values are valid indices (x → x − 1), the same structure Fast & Slow uses in Find the Duplicate Number. Here we use each value's home index as a marker: make it negative the first time; finding it already negative means a duplicate.

Why not another pattern? A set or counter is O(n) extra space; sorting is O(n log n). Floyd's cycle finding returns only one duplicate, not all of them.

Approach:

1. For each x in nums, look at home = abs(x) − 1 (use abs because earlier steps may have negated x).
2. If nums[home] is already negative, abs(x) was seen before: record it.
3. Otherwise negate nums[home] to mark abs(x) as seen.

class Solution:
    def findDuplicates(self, nums: List[int]) -> List[int]:
        duplicates = []
        for i in range(len(nums)):
            value = abs(nums[i])  # the sign may already be used as a marker
            home = value - 1  # the index that represents this value
            if nums[home] < 0:
                duplicates.append(value)  # its marker is set: seen before
            else:
                nums[home] = -nums[home]  # set the marker
        return duplicates

What the code is doing, line by line:

1. abs(nums[i]): the stored number may have been negated as a marker, but its magnitude is the real value.
2. home = value - 1: values 1..n map onto indices 0..n−1.
3. A negative number at home means value was already marked once.
4. Negating the number at home uses the sign bit as a free boolean, so no extra memory is needed.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• No duplicates → [].
• Every value appears twice.
• [1, 1] → [1].

Complexity: O(n) time, O(1) extra space (besides the output).

Problem: Return the smallest positive integer that is not in nums, in O(n) time and O(1) extra space.

Solve it on LeetCode ↗

Constraints: 1 ≤ nums.length ≤ 10⁵ · -2³¹ ≤ nums[i] ≤ 2³¹ - 1

From brute force to the pattern: Checking 1, 2, 3, … with a linear search each time is O(n²); a set is O(n) time but O(n) space; sorting is O(n log n). Because the answer lies in 1..n + 1, each value can be swapped into its own index, and one more scan finds the gap: O(n) time, O(1) space.

Spot it: The answer is always in 1..n + 1 (n numbers can cover at most 1..n). So the array itself can be used as the "seen" table: index v − 1 is the home of value v. Following i → nums[i] − 1 and swapping values home is the cyclic-indices trick, a cousin of fast & slow on i → nums[i] (Find the Duplicate Number).

Why not another pattern? A hash set gives O(n) time but O(n) space, and sorting is O(n log n); both break the constraints. Binary search doesn't apply because the input isn't sorted.

Key insight: Swap each value v in 1..n into position v − 1 until every position holds its own value or a value that has no home (≤ 0, > n, or a duplicate). Then the first index i with nums[i] != i + 1 gives the answer i + 1. Each swap puts one value home for good, so there are at most n swaps in total.

Approach:

1. For each index i: while nums[i] is in 1..n and its home nums[i] − 1 doesn't already hold the same value, swap it home.
2. Values outside 1..n, and duplicates, are left where they are.
3. Scan again: the first index i with nums[i] != i + 1 means i + 1 is missing.
4. If every position is correct, the answer is n + 1.

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        n = len(nums)
        for i in range(n):
            # keep sending nums[i] to its home (index value - 1) while that's possible
            while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
                home = nums[i] - 1  # where this value belongs
                nums[i], nums[home] = nums[home], nums[i]  # move it home
        for i in range(n):
            if nums[i] != i + 1:
                return i + 1  # the first position without its own value
        return n + 1  # 1..n are all present

What the code is doing, line by line:

1. for i in range(n): visit each position once.
2. while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]: the value has a home inside the array, and that home doesn't already contain it (this also stops duplicates from swapping forever).
3. home = nums[i] - 1 then the swap: the value goes home, and whatever was there comes to i to be checked next round.
4. Second loop: the first index whose value isn't i + 1 reveals the smallest missing positive.
5. return n + 1: every number 1..n was present.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• All non-positive, e.g. [-1, -2] → 1.
• Already 1..n, e.g. [1, 2, 3] → 4.
• Duplicates, e.g. [1, 1] → 2 (the != check prevents an endless swap).

Complexity: O(n) time (each swap fixes one value permanently, so at most n swaps in total), O(1) extra space.