LinkedList In-place Reversal

Problem: Reverse the nodes of the list k at a time. If the last group has fewer than k nodes, leave it as it is. Only change links, not values.

Solve it on LeetCode ↗

Constraints: The number of nodes in the list is n. · 1 ≤ k ≤ n ≤ 5000 · 0 ≤ Node.val ≤ 1000

From brute force to the pattern: Copying values into an array, reversing chunks and rebuilding uses O(n) space. Reversing each full group in place with careful reconnection is O(n) time and O(1) space; a dummy node avoids special-casing the first group.

Spot it: "reverse" + "k at a time" + "only nodes may be changed": repeated sub-list reversal with stitching.

Key insight: keep group_prev (the node before the group). First check that k nodes exist (find kth). Reverse the group with prev_node initialised to group_next instead of None: that way the group's old first node automatically points to the rest of the list. Then hook group_prev.next = kth and move group_prev to the old first node (now the group's tail).

Approach:

1. Make a dummy before head; group_prev = dummy.
2. Walk k steps from group_prev to find kth. If you hit None, return dummy.next.
3. Save group_next = kth.next. Reverse the k nodes with prev_node starting at group_next.
4. Stitch: group_prev.next = kth (the new front). The old first node is now the group's tail, so it becomes the next group_prev.
5. Repeat.

class Solution:
    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        # The head changes after the first group, so put a dummy in front.
        dummy = ListNode(0, head)
        # group_prev = the node just BEFORE the group we are working on.
        group_prev = dummy
        while True:
            # --- 1) Is there a full group of k nodes? ---
            # Walk k steps from group_prev. We land on the k-th node of the group.
            kth = group_prev
            for step in range(k):
                kth = kth.next
                if kth is None:
                    # Fewer than k nodes are left: leave them as they are.
                    return dummy.next
            # The first node AFTER this group (it may be None).
            group_next = kth.next
            # The group's first node. After reversing, it will be the group's LAST node.
            group_first = group_prev.next

            # --- 2) Reverse the k nodes of this group (save, flip, step, step). ---
            # Trick: prev_node starts at group_next instead of None, so the old
            # first node automatically ends up pointing at the rest of the list.
            prev_node = group_next
            current = group_first
            while current is not group_next:
                next_node = current.next      # save the rest
                current.next = prev_node      # flip the arrow
                prev_node = current           # step prev_node
                current = next_node           # step current

            # --- 3) Stitch the front of the group back in. ---
            # kth was the group's last node; now it is the group's first node.
            group_prev.next = kth
            # The old first node is now the group's tail, so it is
            # the node BEFORE the next group.
            group_prev = group_first

What the code is doing, line by line:

1. dummy = ListNode(0, head) and group_prev = dummy: the head will change after the first group, so we keep a fake node in front. group_prev always sits just before the group we are working on.
2. while True: handle one group per round. The only way out is the return inside.
3. Check for a full group: starting at group_prev, the for step in range(k) loop walks k nodes. If it falls off the end (kth is None), fewer than k nodes are left, so we stop and return dummy.next without touching them.
4. group_next = kth.next is the first node after the group; group_first = group_prev.next is the group's first node (it will become the group's last node).
5. Reverse the group: the usual save / flip / step / step loop, with one trick: prev_node starts at group_next instead of None. So when group_first is flipped, it points straight at the rest of the list and the back end is already stitched. The loop stops when current reaches group_next.
6. group_prev.next = kth stitches the front: the node before the group now points at the old last node, which is the new first node.
7. group_prev = group_first: the old first node is now the group's tail, so it is the node before the next group.

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

Edge cases to test:

• k = 1 → unchanged.
• Length not a multiple of k: the last partial group stays as is.
• k equal to the length → the whole list reversed.

Complexity: O(n) time (each node visited twice), O(1) space.

Problem: Reverse only positions left..right (1-indexed) of the list, in one pass.

Solve it on LeetCode ↗

Constraints: The number of nodes in the list is n. · 1 ≤ n ≤ 500 · -500 ≤ Node.val ≤ 500 · 1 ≤ left ≤ right ≤ n

From brute force to the pattern: Copying the values between left and right into an array and writing them back reversed uses O(n) space. Reversing in place in a single pass, with a dummy node for left = 1, is O(n) time and O(1) space.

Spot it: "reverse from position left to right". Partial reversal: needs a dummy (left may be 1) and stitching. The second visualizer above traces it.

Key insight: "head insertion": the part's first node (tail) stays put while each following node is unhooked and moved to the front of the part. After right − left moves, the part is reversed and both ends are already connected.

Approach:

1. Create a dummy before head and walk left − 1 steps to reach before.
2. tail = before.next: the part's first node, which will end up last.
3. Repeat right − left times: unhook moved = tail.next and insert it right after before.
4. Return dummy.next.

class Solution:
    def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
        # A dummy node in front of head: a node before the part always exists,
        # even when left == 1.
        dummy = ListNode(0, head)
        # Walk left - 1 steps so that 'before' stops just before position left.
        before = dummy
        for step in range(left - 1):
            before = before.next
        # tail = first node of the part. It stays where it is while the other
        # nodes are moved in front of it, so it ends up last.
        tail = before.next
        # Do right - left moves.
        for move in range(right - left):
            # The node right after tail is the one we move.
            moved = tail.next
            # Unhook it: tail skips over it.
            tail.next = moved.next
            # Insert it at the front of the part (right after 'before').
            moved.next = before.next
            before.next = moved
        # dummy.next is the real head (it changed if left was 1).
        return dummy.next

What the code is doing, line by line:

1. dummy = ListNode(0, head): a fake node before the head, so the node before the part always exists (needed when left == 1).
2. before = dummy, then for step in range(left - 1): before = before.next walks to the node just before position left.
3. tail = before.next: the first node of the part. It stays put while the nodes after it are moved in front of it, so it ends up last.
4. for move in range(right - left): a part of right - left + 1 nodes needs right - left moves.
5. moved = tail.next picks the node right after tail; tail.next = moved.next unhooks it (tail skips over it).
6. moved.next = before.next and before.next = moved insert it at the front of the part, right after before.
7. return dummy.next: the real head of the list.

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

Edge cases to test:

• left == right → unchanged.
• left = 1 (the head changes).
• right is the last node.

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

Problem: Swap every two adjacent nodes (1→2→3→4 becomes 2→1→4→3) without changing values.

Solve it on LeetCode ↗

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

From brute force to the pattern: Swapping the values is simple but is not what's asked (nodes must move). Re-linking each pair in place is O(n) time and O(1) space.

Spot it: it's k-group reversal with k = 2, small enough to write the three re-links by hand.

Key insight: with prev_node → first → second → rest, set first.next = rest, second.next = first, prev_node.next = second. Then first is the new prev_node.

Approach:

1. dummy → head; prev_node = dummy.
2. While two nodes first, second follow prev_node: first.next = second.next, second.next = first, prev_node.next = second.
3. Move prev_node to first (now the second node of the pair).
4. Return dummy.next.

class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # The head changes (the 2nd node becomes the 1st), so use a dummy.
        dummy = ListNode(0, head)
        # prev_node = the node just BEFORE the pair we are about to swap.
        prev_node = dummy
        # A pair needs two nodes after prev_node.
        while prev_node.next is not None and prev_node.next.next is not None:
            # Name the two nodes of the pair.
            first = prev_node.next
            second = prev_node.next.next
            # first skips ahead to whatever comes after the pair.
            first.next = second.next
            # second points back to first.
            second.next = first
            # The node before the pair now points to second (the new front).
            prev_node.next = second
            # first is now the back of the pair, so it is the node
            # before the next pair.
            prev_node = first
        return dummy.next

What the code is doing, line by line:

1. dummy = ListNode(0, head): the second node will become the head, so we use a fake node in front and return dummy.next at the end.
2. prev_node = dummy: the node just before the pair we are about to swap.
3. while prev_node.next is not None and prev_node.next.next is not None: only swap if two nodes follow prev_node. A single leftover node stays where it is.
4. first = prev_node.next and second = prev_node.next.next give the two nodes of the pair names.
5. first.next = second.next: first skips ahead to whatever comes after the pair.
6. second.next = first: second now points back at first.
7. prev_node.next = second: the node before the pair now points at second, the new front of the pair.
8. prev_node = first: first is now the back of the pair, so it is the node before the next pair.

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

Edge cases to test:

• Empty list or a single node → unchanged.
• Odd length: the last node stays put.
• Exactly two nodes.

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

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: you need to walk the first half forwards and the second half backwards at the same time. Reverse the second half in place.

Key insight: find the start of the second half with fast & slow, reverse from there, then walk both halves together.

Approach:

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

class Solution:
    def pairSum(self, head: Optional[ListNode]) -> int:
        # --- 1) Find the first node of the second half (fast & slow). ---
        slow = head
        fast = head
        while fast is not None and fast.next is not None:
            slow = slow.next          # slow moves 1 step
            fast = fast.next.next     # fast moves 2 steps
        # slow is now the first node of the second half.

        # --- 2) Reverse the second half, starting at slow. ---
        prev_node = None
        current = slow
        while current is not None:
            next_node = current.next      # save
            current.next = prev_node      # flip
            prev_node = current           # step
            current = next_node           # step
        # prev_node is the head of the reversed second half (the old last node).

        # --- 3) Walk both halves together and add the twins. ---
        best = 0
        front = head          # walks the first half forwards
        back = prev_node      # walks the second half "backwards"
        while back is not None:
            twin_sum = front.val + back.val
            # Keep the biggest sum seen so far.
            if twin_sum > best:
                best = twin_sum
            front = front.next
            back = back.next
        return best

What the code is doing, line by line:

1. Phase 1: slow and fast both start at the head. Each round slow moves 1 node and fast moves 2. When fast can't move two more nodes, slow is on the first node of the second half (the list has even length).
2. Phase 2: reverse the second half with save / flip / step / step, starting at slow. Afterwards prev_node is the old last node, which is now the head of the reversed second half.
3. Phase 3: front walks the first half from the head; back walks the reversed second half. Node i meets its twin n − 1 − i at the same time.
4. twin_sum = front.val + back.val, and the if twin_sum > best block keeps the largest sum seen so far.
5. Both pointers step forward; the loop ends when back runs out. Return best.

Dry run on LeetCode example head = [5,4,2,1] (expected 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: Reverse the entire list and return the new head.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: The number of nodes in the list is the range [0, 5000]. · -5000 ≤ Node.val ≤ 5000

From brute force to the pattern: Pushing the values on a stack and rebuilding uses O(n) extra space. Re-pointing every next in one pass is O(n) time and O(1) space (the recursive version uses O(n) stack).

Spot it: template A word for word. Interviewers often ask for the recursive version too.

Recursive insight: reverse everything after head; now head.next is the tail of that reversed part, so hang head after it: head.next.next = head, and cut head.next = None.

Approach:

1. Iterative: prev_node = None, current = head; repeat save / flip / step / step until current is None; return prev_node.
2. Recursive base case: an empty or single-node list is its own reverse.
3. Reverse the rest; head.next is now the last node of that reversed part.
4. Call the node after head second; set second.next = head (that is head.next.next = head) and head.next = None, then return the head found by the recursion.

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # Iterative version: template A.
        prev_node = None          # nothing reversed yet
        current = head            # start flipping at the head
        while current is not None:
            next_node = current.next      # 1. save the rest of the list
            current.next = prev_node      # 2. flip the arrow backwards
            prev_node = current           # 3. step prev_node forward
            current = next_node           # 4. step current forward
        # The old tail is the new head.
        return prev_node

    def reverseListRecursive(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # Base case: an empty list or a single node is already reversed.
        if head is None or head.next is None:
            return head
        # Reverse everything AFTER head. new_head is the old last node.
        new_head = self.reverseListRecursive(head.next)
        # head.next still points to the node that came right after head.
        # That node is now the TAIL of the reversed rest.
        second = head.next
        # Hang head after it: the node after me now points back to me.
        second.next = head
        # head is the new tail (for now), so it must point at nothing.
        head.next = None
        return new_head

What the code is doing, line by line:

1. reverseList (iterative): prev_node = None (nothing reversed yet) and current = head.
2. Inside while current is not None: do the four lines in order: save next_node = current.next, flip current.next = prev_node, step prev_node = current, step current = next_node.
3. When current becomes None, prev_node is the old tail = new head, so return it.
4. reverseListRecursive: base case: if the list is empty or has one node, it is already reversed, so return head.
5. new_head = self.reverseListRecursive(head.next) trusts the recursion to reverse everything after head. new_head is the old last node and never changes on the way back up.
6. second = head.next: this node was right after head, and after the recursive call it is the tail of the reversed rest.
7. second.next = head hangs head after it; head.next = None makes head the new tail (otherwise we would get a 2-node cycle).
8. Return new_head so every level passes the same new head upwards.

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

Dry run of reverseListRecursive on head = [1,2,3]. The calls go down to depth 3 first; the rows show them finishing from the deepest call back up:

Edge cases to test:

• Empty list → None.
• A single node.
• Two nodes.

Complexity: O(n) time; O(1) space iterative, O(n) stack recursive.

Problem: Do the list's values read the same forwards and backwards, using only 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: Comparing the front with the back means reading the second half backwards. Reverse it in place instead of copying into an array.

Approach:

1. Find the start of the second half with fast & slow.
2. Reverse the second half with save / flip / step / step.
3. Walk from head and from the reversed half together, comparing values.
4. Any mismatch → False; otherwise True.

class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        # --- 1) Move slow to the start of the second half (fast & slow). ---
        slow = head
        fast = head
        while fast is not None and fast.next is not None:
            slow = slow.next          # 1 step
            fast = fast.next.next     # 2 steps

        # --- 2) Reverse the second half in place. ---
        prev_node = None
        current = slow
        while current is not None:
            next_node = current.next      # save
            current.next = prev_node      # flip
            prev_node = current           # step
            current = next_node           # step

        # --- 3) Walk both halves together and compare values. ---
        front = head          # start of the first half
        back = prev_node      # start of the reversed second half
        while back is not None:
            if front.val != back.val:
                # One mismatch is enough: not a palindrome.
                return False
            front = front.next
            back = back.next
        # Every pair matched.
        return True

What the code is doing, line by line:

1. Phase 1: slow moves 1 node per round and fast moves 2. When fast can't continue, slow is at the start of the second half (for odd length it is the middle node, which is fine: it compares with itself).
2. Phase 2: reverse the second half in place with save / flip / step / step, starting at slow. Afterwards prev_node is the head of the reversed second half.
3. Phase 3: front starts at the head and back at prev_node. While back still has nodes, compare the values.
4. if front.val != back.val: return False: one mismatch is enough to prove it is not a palindrome.
5. Otherwise step both pointers. If the loop ends without a mismatch, every pair matched, so return True.

Dry run on LeetCode example head = [1,2,2,1] (expected True). Two nodes have value 2, so the node position is shown too:

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.

Problem: Rearrange L0 → L1 → … → Ln into L0 → Ln → L1 → Ln−1 → … by changing links only.

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 → split at the middle, reverse the second half, then weave.

Approach:

1. Fast/slow with while fast.next and fast.next.next puts slow at the end of the first half.
2. Cut after slow and reverse the second half.
3. Weave: front.next = back, back.next = front_next, then advance both.
4. Stop when the (shorter or equal) second half runs out.

class Solution:
    def reorderList(self, head: Optional[ListNode]) -> None:
        # 0 or 1 node: nothing to reorder.
        if head is None or head.next is None:
            return

        # --- 1) Move slow to the END 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

        # --- 2) Cut the list in two and reverse the second half. ---
        prev_node = None
        current = slow.next       # the second half starts after slow
        slow.next = None          # cut: the first half now ends at slow
        while current is not None:
            next_node = current.next      # save
            current.next = prev_node      # flip
            prev_node = current           # step
            current = next_node           # step

        # --- 3) Weave the halves: front1, back1, front2, back2, ... ---
        front = head
        back = prev_node
        while back is not None:
            # Remember where each half continues before we change links.
            front_next = front.next
            back_next = back.next
            # front -> back -> (old front.next)
            front.next = back
            back.next = front_next
            # Move both pointers to their saved next nodes.
            front = front_next
            back = back_next

What the code is doing, line by line:

1. if head is None or head.next is None: return: 0 or 1 nodes, nothing to reorder.
2. Phase 1: with the condition fast.next is not None and fast.next.next is not None, slow stops at the end of the first half (the first half gets the extra node when the length is odd).
3. Phase 2: current = slow.next is the start of the second half; slow.next = None cuts the list into two separate lists. Then save / flip / step / step reverses the second half, and prev_node is its new head.
4. Phase 3 (weave): front walks the first half and back the reversed second half. Before changing links, save front_next and back_next.
5. front.next = back and back.next = front_next put one back-node between two front-nodes.
6. Move front and back to their saved next nodes. The loop ends when the second half (never longer than the first) runs out.

Dry run on LeetCode example head = [1,2,3,4,5] (expected [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: Rotate the list to the right by k places: the last k nodes move to the front.

Solve it on LeetCode ↗

Constraints: The number of nodes in the list is in the range [0, 500]. · -100 ≤ Node.val ≤ 100 · 0 ≤ k ≤ 2 * 10⁹

From brute force to the pattern: Rotating one step at a time is O(n · k). Measuring the length once, closing the ring and cutting in the right place is O(n).

Spot it: Re-linking pointers in place, like reversal. The trick is to close the list into a ring and cut it at the right spot.

Approach:

1. Measure the length and find the tail.
2. shift = k % length; if it's 0, return head unchanged.
3. Link tail.next = head to make a ring.
4. Walk length − shift − 1 steps from head to the new tail; the new head is new_tail.next; then cut the ring.

class Solution:
    def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        # 0 or 1 node: rotating changes nothing.
        if head is None or head.next is None:
            return head

        # --- 1) Measure the length and find the tail. ---
        length = 1
        tail = head
        while tail.next is not None:
            tail = tail.next
            length = length + 1

        # --- 2) Rotating by 'length' places changes nothing, so drop full turns. ---
        # shift = how many places we really need to rotate.
        shift = k % length
        if shift == 0:
            return head

        # --- 3) Close the list into a ring. ---
        tail.next = head

        # --- 4) The new tail is length - shift - 1 steps from the head. ---
        new_tail = head
        for step in range(length - shift - 1):
            new_tail = new_tail.next
        # The node after the new tail is the new head.
        new_head = new_tail.next
        # Cut the ring open.
        new_tail.next = None
        return new_head

What the code is doing, line by line:

1. if head is None or head.next is None: return head: 0 or 1 nodes can't change by rotating.
2. length = 1, tail = head, then walk tail to the last node, adding 1 to length per step.
3. shift = k % length: rotating by length places gives the same list back, so only the remainder matters. If shift is 0, return head unchanged.
4. tail.next = head closes the list into a ring.
5. The last shift nodes must move to the front, so the new tail is the node at position length − shift, which is length − shift − 1 steps from the head. The for step in range(length - shift - 1) loop walks there.
6. new_head = new_tail.next, then new_tail.next = None cuts the ring open. Return new_head.

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

Edge cases to test:

• k = 0 or k a multiple of the length → unchanged.
• Empty list or a single node.
• Very large k (e.g. 2·10⁹): you must take % length.

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

Problem: Two non-negative numbers are stored as lists with the most-significant digit first. Return their sum as a list in the same order.

Solve it on LeetCode ↗

Constraints: The number of nodes in each linked list is in the range [1, 100]. · 0 ≤ Node.val ≤ 9 · It is guaranteed that the list represents a number that does not have leading zeros.

From brute force to the pattern: Converting to integers works in Python but defeats the purpose and fails in languages with fixed-size integers. Reversing the lists, adding column by column with a carry, and reversing back is O(m + n).

Spot it: Addition starts from the least-significant digit, which is at the end. Reverse both lists in place first.

Key insight: Build the answer by prepending each new digit node. It comes out most-significant first, so no final reversal is needed.

Approach:

1. Reverse both input lists (template A).
2. Add digit by digit with a carry: digit = total % 10 and carry = total // 10.
3. Prepend a node for digit to the result.
4. Continue while either list or the carry remains.

class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        # --- 1) Reverse both lists so the ones digit comes first. ---
        first = self.reverse_list(l1)
        second = self.reverse_list(l2)

        # --- 2) Add digit by digit, like on paper, keeping a carry. ---
        carry = 0
        result = None             # the answer list, built from the back
        while first is not None or second is not None or carry != 0:
            total = carry
            # Add the digit from the first number, if it still has digits.
            if first is not None:
                total = total + first.val
                first = first.next
            # Add the digit from the second number, if it still has digits.
            if second is not None:
                total = total + second.val
                second = second.next
            digit = total % 10        # the digit we write down
            carry = total // 10       # the 1 we carry to the next column
            # PREPEND the new digit: put it in front of the answer so far.
            # The answer then comes out most-significant digit first.
            new_node = ListNode(digit)
            new_node.next = result
            result = new_node
        return result

    def reverse_list(self, head):
        # Template A: save, flip, step, step.
        prev_node = None
        current = head
        while current is not None:
            next_node = current.next
            current.next = prev_node
            prev_node = current
            current = next_node
        return prev_node

What the code is doing, line by line:

1. first = self.reverse_list(l1) and second = self.reverse_list(l2): the helper method at the bottom is template A. After reversing, each list starts with its ones digit, which is where adding starts.
2. carry = 0 and result = None: no carry yet and an empty answer list.
3. while first is not None or second is not None or carry != 0: keep going while either number still has digits or a carry is left over (e.g. 99 + 1 needs an extra digit).
4. total = carry, then each if block adds that number's digit (only if it still has one) and moves its pointer forward. This replaces the compact a.val if a else 0 trick.
5. digit = total % 10 is the digit we write down; carry = total // 10 is the 1 (or 0) carried to the next column.
6. new_node.next = result then result = new_node prepends the digit. We produce digits ones-first, and prepending each one puts the answer most-significant-first, as required.
7. Return result.

Dry run on LeetCode example l1 = [7,2,4,3], l2 = [5,6,4] (7243 + 564 = 7807, expected [7,8,0,7]):

Edge cases to test:

• Different lengths, e.g. [7, 2, 4, 3] + [5, 6, 4].
• A final carry adds a new leading digit, e.g. [5] + [5] → [1, 0].
• One number is 0.

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

Problem: Split the list into consecutive groups of sizes 1, 2, 3, … (the last group may be shorter). Reverse every group whose actual length is even.

Solve it on LeetCode ↗

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

From brute force to the pattern: Copying values into an array, reversing even-length chunks and writing them back uses O(n) space. Walking group by group and reversing in place is O(n) time and O(1) space.

Spot it: Reversing chunks in place → k-group reversal where k grows each time and a parity check decides whether to reverse.

Approach:

1. group_prev = head (group 1 has size 1 and is never reversed); group_size = 2.
2. Count up to group_size nodes after group_prev to get the group's real length.
3. If it's even, reverse those nodes with prev_node starting at group_next (the node after the group), set group_prev.next = prev_node, and move group_prev to group_first (the old first node).
4. If it's odd, move group_prev to group_last (the group's last node).
5. group_size = group_size + 1; repeat until no nodes remain.

class Solution:
    def reverseEvenLengthGroups(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # Group 1 is just the head (size 1, odd), so it is never reversed.
        # group_prev = the node just BEFORE the current group.
        group_prev = head
        group_size = 2            # the size the next group SHOULD have
        while group_prev.next is not None:
            # --- 1) Count the real length of this group (the last may be shorter). ---
            group_last = group_prev
            count = 0
            while count < group_size and group_last.next is not None:
                group_last = group_last.next
                count = count + 1

            if count % 2 == 0:
                # --- 2a) Even length: reverse the group (like k-group). ---
                group_first = group_prev.next
                group_next = group_last.next
                # Start prev_node at group_next so the old first node
                # ends up pointing at the rest of the list.
                prev_node = group_next
                current = group_first
                while current is not group_next:
                    next_node = current.next      # save
                    current.next = prev_node      # flip
                    prev_node = current           # step
                    current = next_node           # step
                # Stitch the front: prev_node is the old last node = new first node.
                group_prev.next = prev_node
                # The old first node is now the group's tail.
                group_prev = group_first
            else:
                # --- 2b) Odd length: leave it alone, just jump over it. ---
                group_prev = group_last

            # The next group should be one node longer.
            group_size = group_size + 1
        return head

What the code is doing, line by line:

1. group_prev = head: group 1 is just the head. Its size is 1 (odd), so it is never reversed, and the head never changes. That's why no dummy is needed.
2. group_size = 2: the size the next group should have. It grows by 1 after every group.
3. while group_prev.next is not None: continue while there are nodes after the last finished group.
4. Count the real length: walk group_last forward up to group_size nodes, counting them in count. The last group may be shorter, which is why we use count (not group_size) to decide.
5. Even count: name group_first and group_next, then reverse with save / flip / step / step, starting prev_node at group_next (same trick as problem 25) so the old first node points at the rest of the list.
6. group_prev.next = prev_node stitches the front (prev_node is the old last node = new first). group_prev = group_first, because the old first node is now the group's tail.
7. Odd count: leave the group alone and jump over it: group_prev = group_last.
8. group_size = group_size + 1, then do the next group. Return head at the end.

Dry run on LeetCode example head = [5,2,6,3,9,1,7,3,8,4] (expected [5,6,2,3,9,1,4,8,3,7]):

Edge cases to test:

• The last group is shorter and its length is even → reverse it.
• The last group is shorter and odd → leave it.
• A list of 1 or 2 nodes.

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

Problem: Merge two sorted linked lists into one sorted list by splicing their nodes together. Return the new head.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: The number of nodes in both lists is in the range [0, 50]. · -100 ≤ Node.val ≤ 100 · Both list1 and list2 are sorted in non-decreasing order.

From brute force to the pattern: Copying all values into an array, sorting and rebuilding is O((m + n) log(m + n)) and allocates new nodes. Merging by re-linking the existing nodes is O(m + n) time and O(1) extra space.

Spot it: Two sorted sequences → compare the two fronts and take the smaller (the merge step of merge sort). With linked lists we re-point next pointers instead of copying values.

Approach:

1. Create a dummy node and a tail pointer.
2. While both lists have nodes: attach the smaller front node to tail, advance that list, and move tail.
3. One list may have nodes left. They are already sorted, so attach the rest in one step.
4. Return dummy.next.

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode()   # placeholder in front of the merged list
        tail = dummy
        while list1 is not None and list2 is not None:
            if list1.val <= list2.val:
                tail.next = list1      # reuse list1's node
                list1 = list1.next
            else:
                tail.next = list2
                list2 = list2.next
            tail = tail.next
        # at most one list still has nodes, and they are already sorted
        if list1 is not None:
            tail.next = list1
        else:
            tail.next = list2
        return dummy.next

What the code is doing, line by line:

1. dummy, tail: tail is always the last node of the merged list so far.
2. while list1 is not None and list2 is not None: compare only while both have a front node.
3. if list1.val <= list2.val: take the smaller front. <= keeps equal values in their original order (a stable merge).
4. tail.next = list1 re-uses the existing node; list1 = list1.next moves that list forward; tail = tail.next moves to the new end.
5. After the loop, attach whichever list is left. It's already sorted and bigger than everything placed so far.

Dry run on the example:

list1 = [1, 2, 4], list2 = [1, 3, 4] (LeetCode Example 1). Returns [1, 1, 2, 3, 4, 4].

Edge cases to test:

• One or both lists empty.
• Equal values in both lists.
• Every value of one list smaller than every value of the other.

Complexity: O(m + n) time, O(1) extra space (nodes are re-linked, not copied).

Problem: The linked list is sorted. Delete duplicates so each value appears only once, and return the head.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: The number of nodes in the list is in the range [0, 300]. · -100 ≤ Node.val ≤ 100 · The list is guaranteed to be sorted in ascending order.

From brute force to the pattern: A set of seen values plus rebuilding the list uses O(n) space. Because the list is sorted, comparing each node with its neighbour removes duplicates in place: O(n) time, O(1) space.

Spot it: Sorted means equal values sit next to each other. Stay on a node and unlink its next for as long as it has the same value. That's in-place pointer surgery with one pointer.

Approach:

1. cur = head.
2. While cur and cur.next exist: if cur.next.val == cur.val, unlink cur.next (cur.next = cur.next.next) and stay on cur.
3. Otherwise move cur forward.
4. Return head (the first node is never removed).

class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        cur = head
        while cur is not None and cur.next is not None:
            if cur.next.val == cur.val:
                # same value again: unlink the next node, but stay here
                # (the new next might be another copy)
                cur.next = cur.next.next
            else:
                # a new value: move on to it
                cur = cur.next
        return head

What the code is doing, line by line:

1. cur = head: the node whose duplicates we are removing.
2. while cur is not None and cur.next is not None: we look one node ahead, so both must exist.
3. if cur.next.val == cur.val: cur.next = cur.next.next: drop the copy. We do not move cur, because a run like 1 → 1 → 1 needs several removals.
4. else: cur = cur.next: the next value is different, so it becomes the new current node.
5. return head: the head is the first of its value, so it always stays.

Dry run on the example:

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

Edge cases to test:

• An empty list.
• All values equal → one node remains.
• Duplicates at the end of the list.

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

Problem: Two non-empty linked lists store non-negative integers with their digits in reverse order (2 → 4 → 3 is 342). Return their sum as a linked list in the same reverse format.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: The number of nodes in each linked list is in the range [1, 100]. · 0 ≤ Node.val ≤ 9 · It is guaranteed that the list represents a number that does not have leading zeros.

From brute force to the pattern: Converting both lists to integers and back works in Python but would overflow in most languages and misses the point. Column addition with a carry, one node at a time, is O(max(m, n)).

Spot it: Reverse order means the head is the ones digit, exactly where column addition starts. So walk both lists together, add digit + digit + carry, and append one new node per column.

Approach:

1. Make a dummy node and a tail pointer to append to; carry = 0.
2. While either list has nodes left or carry is not zero: add the two current digits (0 for a list that has ended) and carry.
3. The new digit is total % 10; the new carry is total // 10. Append the digit and move tail.
4. Advance whichever input lists still have nodes.
5. Return dummy.next.

class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode()   # the answer is built after this placeholder
        tail = dummy
        carry = 0
        # a final carry (e.g. 5 + 5 = 10) still needs its own node
        while l1 is not None or l2 is not None or carry != 0:
            total = carry
            if l1 is not None:
                total = total + l1.val
                l1 = l1.next
            if l2 is not None:
                total = total + l2.val
                l2 = l2.next
            # write the ones digit, carry the tens digit to the next column
            tail.next = ListNode(total % 10)
            tail = tail.next
            carry = total // 10
        return dummy.next

What the code is doing, line by line:

1. dummy, tail: appending after a placeholder means the first digit needs no special case.
2. while l1 is not None or l2 is not None or carry != 0: keep going while any digit or carry remains. The lists can have different lengths.
3. total = carry, then add l1.val and l2.val only if that list still has a node, stepping it forward as we use it.
4. ListNode(total % 10): the digit for this column (e.g. 10 → 0). carry = total // 10 is 0 or 1 for the next column.
5. return dummy.next: skip the placeholder.

Dry run on the example:

l1 = [2, 4, 3] (342), l2 = [5, 6, 4] (465) (LeetCode Example 1). Returns [7, 0, 8] (807).

Edge cases to test:

• Different lengths.
• A carry at the very end, e.g. [9, 9] + [1] → [0, 0, 1].
• Both numbers are 0.

Complexity: O(max(m, n)) time, O(max(m, n)) for the output list.

Problem: The linked list is sorted. Delete every node whose value appears more than once, leaving only values that were distinct. Return the head.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: The number of nodes in the list is in the range [0, 300]. · -100 ≤ Node.val ≤ 100 · The list is guaranteed to be sorted in ascending order.

From brute force to the pattern: Counting each value's occurrences and rebuilding the list uses O(n) space. Since the list is sorted, duplicates form runs that can be skipped in place: O(n) time, O(1) space.

Spot it: Unlike LeetCode 83, the first copy must go too, and that may be the head. A dummy node plus a prev pointer that always sits on the last node we are sure to keep makes this a clean in-place splice.

Approach:

1. dummy → head; prev = dummy (the last kept node), cur = head.
2. If cur starts a run of equal values (cur.next has the same value), walk cur to the last node of the run, then splice the whole run out: prev.next = cur.next.
3. Otherwise cur is unique: keep it by moving prev onto it.
4. Move cur forward and repeat. Return dummy.next.

class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(0, head)   # the head itself may be deleted
        prev = dummy                # last node we are sure to keep
        cur = head
        while cur is not None:
            if cur.next is not None and cur.next.val == cur.val:
                # cur starts a run of duplicates: walk to the run's last node
                while cur.next is not None and cur.next.val == cur.val:
                    cur = cur.next
                # cut the whole run out; prev stays where it is
                prev.next = cur.next
            else:
                # cur is unique: it stays, so prev moves onto it
                prev = cur
            cur = cur.next
        return dummy.next

What the code is doing, line by line:

1. dummy = ListNode(0, head): lets us delete the head with the same code as any other node.
2. prev: the last node that is definitely in the answer. We only ever splice after it.
3. if cur.next is not None and cur.next.val == cur.val: cur is the first node of a duplicate run.
4. Inner while: move cur to the last copy of that value.
5. prev.next = cur.next: one assignment removes the entire run. prev does not move: the next node might start another run.
6. else: prev = cur: a value with no copies is kept.
7. cur = cur.next: continue after the run (or after the kept node).

Dry run on the example:

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

Edge cases to test:

• All values duplicated → empty list.
• The head is part of a duplicate run.
• No duplicates → unchanged.

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

Problem: Each node has a next pointer and a random pointer that may point to any node or None. Return a deep copy: brand-new nodes whose pointers mirror the original structure.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: 0 ≤ n ≤ 1000 · -10⁴ ≤ Node.val ≤ 10⁴ · Node.random is null or is pointing to some node in the linked list.

From brute force to the pattern: Searching the list to find where each random points is O(n²). An old → new hash map makes every lookup O(1): two passes, O(n). (Weaving the copies between the originals gets the space down to O(1).)

Spot it: The trouble is random: it may point to a node whose copy doesn't exist yet. A hash map from old node → new node solves it. Create all copies first, then connect them.

Key insight: Two passes. Pass 1 creates a copy of every node. Pass 2 sets copy.next = old_to_new[old.next] and copy.random = old_to_new[old.random]. Mapping None → None avoids special cases. (An O(1)-space variant weaves copies between the originals, but the map version is far easier to get right.)

Approach:

1. Start the map with {None: None}, so a missing pointer copies to a missing pointer.
2. Pass 1: walk the list and create Node(old.val) for every node, storing old → copy.
3. Pass 2: walk again and set each copy's next and random by looking up the copies of the old targets.
4. Return the copy of head.

class Solution:
    def copyRandomList(self, head: "Optional[Node]") -> "Optional[Node]":
        # old node -> its copy; None maps to None so empty pointers copy for free
        old_to_new = {None: None}
        # pass 1: make a copy of every node (pointers not set yet)
        cur = head
        while cur is not None:
            old_to_new[cur] = Node(cur.val)
            cur = cur.next
        # pass 2: wire up next and random using the copies
        cur = head
        while cur is not None:
            copy = old_to_new[cur]
            copy.next = old_to_new[cur.next]
            copy.random = old_to_new[cur.random]
            cur = cur.next
        return old_to_new[head]

What the code is doing, line by line:

1. old_to_new = {None: None}: nodes can be dictionary keys (by identity). Seeding None means old_to_new[cur.random] works even when random is empty.
2. Pass 1, old_to_new[cur] = Node(cur.val): every copy exists before we connect anything, so pass 2 can point to any of them.
3. Pass 2, copy.next = old_to_new[cur.next]: the copy's next is the copy of the old next, never the old node itself.
4. copy.random = old_to_new[cur.random]: same idea for the random pointer.
5. return old_to_new[head]: the copied head (or None for an empty list).

Dry run on the example:

head = [[7, null], [13, 0], [11, 4], [10, 2], [1, 0]] (LeetCode Example 1; each pair is [value, index that random points to]). Name the originals A..E and the copies A'..E'.

Pass 1 already created A'..E', so every lookup in pass 2 succeeds. The copy has the same shape, [[7, null], [13, 0], [11, 4], [10, 2], [1, 0]], with no shared nodes.

Edge cases to test:

• An empty list.
• random pointing to the node itself.
• random is None everywhere.

Complexity: O(n) time, O(n) space for the map.

Problem: Between every pair of adjacent nodes, insert a new node whose value is the greatest common divisor (GCD) of the two values. Return the head.

Solve it on LeetCode ↗ · Video walkthrough ↗

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

From brute force to the pattern: Collecting values into an array and building a new list works but allocates the whole list again. Inserting in place while walking once is O(n · log(max value)) for the GCDs.

Spot it: Pure in-place pointer surgery: for each pair (cur, cur.next), create a node, point it at cur.next, point cur at it, then jump over it to the old next node.

Approach:

1. cur = head.
2. While cur.next exists: compute g = gcd(cur.val, cur.next.val).
3. Create ListNode(g, cur.next): it already points at the old next node. Then set cur.next to the new node.
4. Jump cur two steps (over the new node) to the old next node, and repeat.

class Solution:
    def insertGreatestCommonDivisors(self, head: Optional[ListNode]) -> Optional[ListNode]:
        def gcd(a, b):
            # Euclid: gcd(a, b) = gcd(b, a % b), and gcd(a, 0) = a
            while b != 0:
                a, b = b, a % b
            return a

        cur = head
        while cur is not None and cur.next is not None:
            after = cur.next
            # the new node points at the old next node ...
            middle = ListNode(gcd(cur.val, after.val), after)
            # ... and cur points at the new node
            cur.next = middle
            # skip over the node we just added
            cur = after
        return head

What the code is doing, line by line:

1. def gcd(a, b): Euclid's algorithm: replace (a, b) with (b, a % b) until b is 0; then a is the GCD. (Python's math.gcd does the same.)
2. while cur is not None and cur.next is not None: we need a pair, so the next node must exist.
3. after = cur.next: remember the old neighbour before we change any pointer.
4. middle = ListNode(gcd(...), after): build the new node already linked to after.
5. cur.next = middle: link it in. The order matters: if we changed cur.next first without saving after, we would lose the rest of the list.
6. cur = after: move to the next original node, skipping the one we inserted.

Dry run on the example:

head = [18, 6, 10, 3] (LeetCode Example 1). Returns [18, 6, 6, 2, 10, 1, 3].

Edge cases to test:

• A single node → nothing to insert.
• Equal neighbours: the GCD is the value itself.
• Coprime neighbours → 1.

Complexity: O(n · log(max value)) time (one GCD per pair), O(1) extra space besides the new nodes.

Problem: Rearrange the list so all nodes with values less than x come before nodes ≥ x, preserving the original order within each group.

Solve it on LeetCode ↗

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

From brute force to the pattern: Collecting values into two arrays and rebuilding new nodes is O(n) time but O(n) extra space. Re-linking the existing nodes into two chains needs O(1) space.

Spot it: Splitting one list into two order-preserving groups is in-place pointer surgery: walk once and append each node to the tail of one of two dummy-headed lists, then join them.

Why not another pattern? Copying values into arrays and rebuilding works but allocates new nodes. Swapping values in place would break the relative order.

Approach:

1. Create two dummy heads: small and big, with tails.
2. Walk the list; append each node to the small tail if val < x, else to the big tail.
3. End the big list with None (its last node may still point somewhere), then link small_tail.next = big_head.next.

class Solution:
    def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]:
        small = ListNode()  # dummy head for values < x
        big = ListNode()  # dummy head for values >= x
        small_tail = small
        big_tail = big
        cur = head
        while cur is not None:
            if cur.val < x:
                small_tail.next = cur  # append to the "small" list
                small_tail = cur
            else:
                big_tail.next = cur  # append to the "big" list
                big_tail = cur
            cur = cur.next
        big_tail.next = None  # cut off the old link to avoid a cycle
        small_tail.next = big.next  # small list, then big list
        return small.next

What the code is doing, line by line:

1. Two dummy heads mean the first node of either group needs no special case.
2. Each node is re-linked onto one of the two tails in the order it's visited, which preserves relative order.
3. big_tail.next = None: the last big node might still point to a small node from the original list.
4. small_tail.next = big.next joins the groups; small.next is the new head.

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 values less than x (or all ≥ x).
• An empty list.
• Forgetting big_tail.next = None creates a cycle.

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

Problem: Convert a sorted singly linked list into a height-balanced binary search tree.

Solve it on LeetCode ↗

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

From brute force to the pattern: Finding the middle node at every level with fast/slow pointers costs O(n) per level: O(n log n). Building in in-order uses each list node exactly once at the moment it's needed: O(n).

Spot it: The list is the BST's in-order sequence. Build the tree in in-order: recursively build the left half, take the current list node as the root, then build the right half, advancing one pointer through the list as you go.

Why not another pattern? Copying the list into an array and taking middles (LeetCode 108) is O(n) time but O(n) extra space. Finding the middle with fast/slow at every level is O(n log n).

Approach:

1. Count the nodes n.
2. build(lo, hi) builds the tree for list positions lo..hi. If lo > hi, return None.
3. mid = (lo + hi) // 2; build the left subtree for lo..mid − 1 first; this consumes exactly the nodes before mid.
4. The current list node is now position mid: make it the root, advance the list pointer, then build the right subtree mid + 1..hi.

class Solution:
    def sortedListToBST(self, head: Optional[ListNode]) -> Optional[TreeNode]:
        n = 0
        cur = head
        while cur is not None:
            n = n + 1  # count the nodes
            cur = cur.next
        self.cur = head  # the next list node to place (in-order)

        def build(lo, hi):
            if lo > hi:
                return None
            mid = (lo + hi) // 2
            left = build(lo, mid - 1)  # all nodes before mid are consumed here
            root = TreeNode(self.cur.val)  # the current list node is position mid
            self.cur = self.cur.next
            root.left = left
            root.right = build(mid + 1, hi)
            return root

        return build(0, n - 1)

What the code is doing, line by line:

1. Counting first lets build split ranges by index, exactly like the array version.
2. self.cur walks the list in order; an in-order construction visits positions in increasing order too, so they stay in sync.
3. The left subtree is built before the root is created, so by then self.cur points at position mid.
4. Picking the middle of each range keeps the tree balanced.

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:

• An empty list → None.
• One or two nodes.
• Negative values.

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

Problem: Sort a singly linked list using insertion sort and return its head.

Solve it on LeetCode ↗

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

From brute force to the pattern: Copying values into an array, sorting and rebuilding uses O(n) space. Splicing nodes keeps it in place.

Spot it: Insertion sort on a linked list is pure pointer surgery: detach each node and splice it into its place in a growing sorted list behind a dummy head (no shifting of elements needed).

Why not another pattern? Merge sort (LeetCode 148) is O(n log n) and faster; this problem asks specifically for insertion sort (O(n²) worst case).

Approach:

1. dummy starts an empty sorted list.
2. Take nodes from the input one at a time (remember next before re-linking).
3. Walk prev from dummy until prev.next is None or larger than the node; splice the node after prev.

class Solution:
    def insertionSortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode()  # head of the sorted part
        cur = head
        while cur is not None:
            nxt = cur.next  # remember the rest of the unsorted list
            prev = dummy
            while prev.next is not None and prev.next.val < cur.val:
                prev = prev.next  # find where cur belongs
            cur.next = prev.next  # splice cur in after prev
            prev.next = cur
            cur = nxt
        return dummy.next

What the code is doing, line by line:

1. dummy.next is the sorted list built so far (initially empty).
2. nxt = cur.next: save it before cur is re-linked into the sorted list.
3. The inner loop stops at the last node smaller than cur.
4. Two pointer assignments insert cur there.

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:

• Already sorted (each insertion walks to the end; you can optimise by starting from the last inserted node).
• Reverse sorted.
• Duplicates.

Complexity: O(n²) time in the worst case, O(1) extra space.

Problem: You're given only the node to delete (not the head). It's not the last node. Delete it so the list's values no longer contain it.

Solve it on LeetCode ↗

Constraints: The number of the nodes in the given list is in the range [2, 1000]. · -1000 ≤ Node.val ≤ 1000 · The value of each node in the list is unique. · The node to be deleted is in the list and is not a tail node.

From brute force to the pattern: Normally you'd find the previous node from the head (O(n)), but there's no head. The copy-and-skip trick is O(1).

Spot it: A linked-list rewiring puzzle: without the previous node you can't unlink node itself, but you can copy the next node's value into it and unlink the next node.

Why not another pattern? Walking from the head to find the previous node is impossible here: you aren't given the head.

Approach:

1. Copy node.next.val into node.val.
2. Skip over the next node: node.next = node.next.next.

class Solution:
    def deleteNode(self, node):
        node.val = node.next.val  # take over the next node's value
        node.next = node.next.next  # and remove the next node

What the code is doing, line by line:

1. We can't change the previous node's pointer, so we make node look like its successor.
2. Then the successor (now a duplicate) is unlinked.

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:

• Deleting the second-to-last node.
• Equal values in the list.
• The problem guarantees node isn't the tail.

Complexity: O(1) time and space.

Problem: Group all nodes at odd positions first, then those at even positions (1-indexed), keeping the order inside each group, in O(1) space.

Solve it on LeetCode ↗

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

From brute force to the pattern: Collecting nodes into two arrays and re-linking uses O(n) space; weaving the chains in place uses O(1).

Spot it: Splitting a list into two interleaved chains and re-joining them is in-place pointer surgery with two moving pointers.

Why not another pattern? Copying values into arrays and rebuilding uses O(n) extra space, which the problem forbids.

Approach:

1. odd = head, even = head.next, remember even_head.
2. While even and even.next exist: odd.next = even.next, advance odd; even.next = odd.next, advance even.
3. Attach the even chain: odd.next = even_head.

class Solution:
    def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if head is None:
            return None
        odd = head
        even = head.next
        even_head = even  # remember where the even chain starts
        while even is not None and even.next is not None:
            odd.next = even.next  # next odd node
            odd = odd.next
            even.next = odd.next  # next even node
            even = even.next
        odd.next = even_head  # odds first, then evens
        return head

What the code is doing, line by line:

1. odd and even are the tails of the two chains being built.
2. Each round links one odd node and one even node, skipping over the other chain's node.
3. The loop condition guarantees even.next (the next odd node) exists.
4. Finally the odd chain's tail points to the first even node.

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:

• An empty list or a single node.
• Two nodes → unchanged.
• Odd and even lengths.

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

Problem: Implement a singly linked list with get(index), addAtHead, addAtTail, addAtIndex(index, val) and deleteAtIndex(index).

Solve it on LeetCode ↗

Constraints: 0 ≤ index, val ≤ 1000 · Please do not use the built-in LinkedList library. · At most 2000 calls will be made to get, addAtHead, addAtTail, addAtIndex and deleteAtIndex.

From brute force to the pattern: Without a sentinel, inserting or deleting at index 0 needs separate code paths; the dummy node makes every position uniform.

Spot it: Every operation is "walk to the node before position index, then re-link". A dummy (sentinel) head makes index 0 behave like any other position, and a size counter answers bounds checks in O(1).

Why not another pattern? A Python list would make this trivial, but the exercise is about the pointer operations themselves.

Approach:

1. Keep self.dummy (sentinel before the real head) and self.size.
2. A helper _before(index) walks index steps from the dummy: it returns the node just before position index.
3. addAtIndex: reject index > size; splice a new node after _before(index). Head and tail additions are addAtIndex(0, …) and addAtIndex(size, …).
4. get and deleteAtIndex: reject index ≥ size; use _before(index) to read or unlink.

class MyLinkedList:
    class Node:
        def __init__(self, val, nxt=None):
            self.val = val
            self.next = nxt

    def __init__(self):
        self.dummy = self.Node(0)  # sentinel in front of the real head
        self.size = 0

    def _before(self, index):
        node = self.dummy
        for _ in range(index):
            node = node.next  # walk to the node just before position index
        return node

    def get(self, index: int) -> int:
        if index < 0 or index >= self.size:
            return -1
        return self._before(index).next.val

    def addAtHead(self, val: int) -> None:
        self.addAtIndex(0, val)

    def addAtTail(self, val: int) -> None:
        self.addAtIndex(self.size, val)

    def addAtIndex(self, index: int, val: int) -> None:
        if index < 0 or index > self.size:
            return  # invalid position: do nothing
        prev = self._before(index)
        prev.next = self.Node(val, prev.next)  # splice the new node in
        self.size = self.size + 1

    def deleteAtIndex(self, index: int) -> None:
        if index < 0 or index >= self.size:
            return
        prev = self._before(index)
        prev.next = prev.next.next  # unlink the node at index
        self.size = self.size - 1

What the code is doing, line by line:

1. self.dummy sits before position 0, so inserting at the head is the same code as inserting anywhere.
2. _before(index) takes index steps from the dummy, landing on the predecessor of position index.
3. addAtIndex allows index == size (append) but not beyond it.
4. get and deleteAtIndex require an existing position: index < size.

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:

• addAtIndex(size, val) appends.
• addAtIndex(size + 1, val) does nothing.
• Deleting the only node.

Complexity: O(index) per operation (O(n) worst case), O(1) for addAtHead; O(n) space.

Problem: A critical point is a local maximum or minimum (strictly greater or smaller than both neighbours). Return [min distance, max distance] between any two critical points, or [-1, -1] if there are fewer than two.

Solve it on LeetCode ↗

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

From brute force to the pattern: Collecting every critical index and comparing all pairs is O(k²). Only consecutive gaps and the first/last pair matter, so one pass suffices.

Spot it: A single walk looking at each node with its neighbours (prev, cur, cur.next): linked-list traversal with a few remembered indices.

Why not another pattern? Collecting all critical indices in a list first works too (O(k) extra space); you only need the first, previous and latest ones.

Approach:

1. Walk with prev and cur, keeping the position i of cur.
2. If cur is a local max or min, it's critical: compare with the previous critical index for the minimum gap, remember the first one for the maximum.
3. At the end, the maximum distance is last − first; return [-1, -1] if fewer than two critical points.

class Solution:
    def nodesBetweenCriticalPoints(self, head: Optional[ListNode]) -> List[int]:
        first = -1  # index of the first critical point
        last = -1  # index of the latest critical point
        min_gap = float("inf")
        prev = head
        cur = head.next
        i = 1
        while cur is not None and cur.next is not None:
            nxt = cur.next
            if (cur.val > prev.val and cur.val > nxt.val) or (cur.val < prev.val and cur.val < nxt.val):
                if first == -1:
                    first = i  # the first critical point
                else:
                    min_gap = min(min_gap, i - last)  # distance to the previous critical point
                last = i
            prev = cur
            cur = nxt
            i = i + 1
        if min_gap == float("inf"):
            return [-1, -1]  # fewer than two critical points
        return [min_gap, last - first]

What the code is doing, line by line:

1. The first and last nodes can't be critical (they lack a neighbour), so the walk starts at index 1 and stops before the tail.
2. A node is critical when it's strictly above both neighbours or strictly below both.
3. The minimum distance is always between two consecutive critical points, so comparing with last is enough.
4. The maximum distance is between the first and the last critical point.

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:

• Fewer than three nodes → [-1, -1].
• Exactly one critical point → [-1, -1].
• Equal neighbours are not critical (strictly greater/smaller is required).

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

Problem: Insert insertVal into a sorted circular linked list (given any node) so it stays sorted; return the given node (or the new one if empty).

Solve it on LeetCode ↗ (Premium)

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

From brute force to the pattern: Copying to an array and rebuilding is O(n) space; one walk is O(1).

Spot it: A linked-list walk with three cases: a gap prev ≤ x ≤ next; the wrap point (prev > next), where a new maximum or minimum belongs; or a full circle with all equal values (insert anywhere).

Why not another pattern? Finding the minimum first and then scanning works, but one loop handles every case.

Approach:

1. Empty list: a single node pointing to itself.
2. Walk prev = head, cur = head.next once around.
3. Insert when prev.val ≤ x ≤ cur.val, or at the wrap (prev.val > cur.val) when x ≥ prev.val or x ≤ cur.val.
4. If no spot was found after a full circle (all equal), insert after prev.

class Solution:
    def insert(self, head: "Optional[Node]", insertVal: int) -> "Node":
        node = Node(insertVal)
        if head is None:
            node.next = node  # a circle of one
            return node
        prev, cur = head, head.next
        while True:
            if prev.val <= insertVal <= cur.val:
                break  # fits between two neighbours
            if prev.val > cur.val and (insertVal >= prev.val or insertVal <= cur.val):
                break  # at the wrap point: new max or new min
            prev, cur = cur, cur.next
            if prev is head:
                break  # went all the way round (all values equal)
        prev.next = node
        node.next = cur
        return head

What the code is doing, line by line:

1. The wrap point is the only place where values drop; values beyond either end go there.
2. If every value is equal, no condition fires before returning to head, and any position is sorted.

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:

• Empty list.
• All values equal.
• New maximum or minimum.

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

Problem: Swap the values of the k-th node from the start and the k-th node from the end.

Solve it on LeetCode ↗

Constraints: The number of nodes in the list is n. · 1 ≤ k ≤ n ≤ 10⁵ · 0 ≤ Node.val ≤ 100

From brute force to the pattern: Copying to an array is O(n) space; two pointers are O(1).

Spot it: The k-th from the end is found with the gap technique: once a pointer has gone k steps, start a second pointer at the head; when the first reaches the end, the second is k from the end. Then swap the two values.

Why not another pattern? Counting the length first works too (two passes); copying to an array uses O(n) space.

Approach:

1. Walk k − 1 steps from the head: that's first.
2. fast = first, second = head; advance both until fast is the last node.
3. Swap first.val and second.val.

class Solution:
    def swapNodes(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        first = head
        for _ in range(k - 1):
            first = first.next  # k-th from the start
        fast, second = first, head
        while fast.next:
            fast = fast.next  # keep a gap of k - 1 nodes
            second = second.next
        first.val, second.val = second.val, first.val  # k-th from the end is `second`
        return head

What the code is doing, line by line:

1. When fast is at the last node, second is k − 1 nodes behind it: the k-th from the end.
2. Swapping values is allowed and avoids relinking edge cases.

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:

• Both positions are the same node (odd middle).
• k = 1 (first and last).
• Two nodes.

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