LeetCode 143 - Reorder List

2026-07-13

medium　linked list　two pointers　recursion

You are given the head of a singly linked list.

The list of length n starts as:

[0, 1, 2, 3, ..., n-1]

Reorder it to:

[0, n-1, 1, n-2, 2, n-3, ...]

You may not modify node values — only reorder the nodes themselves.

Example 1:

Input: head = [2,4,6,8]

Output: [2,8,4,6]

Example 2:

Input: head = [2,4,6,8,10]

Output: [2,10,4,8,6]

Constraints:

• 1 <= list length <= 1,000
• 1 <= Node.val <= 1,000

Solution 1:

class Solution:
    def reorderList(self, head: Optional[ListNode]) -> None:
        # Approach: Collect into Array, Then Interleave with Two Pointers
        # 1. Traverse the list once, storing all node references in an array.
        # 2. Use left and right pointers starting at both ends.
        # 3. Each iteration: wire left node → right node → next left node,
        #    then advance left forward and right backward.
        # 4. Stop when pointers meet (odd length) or cross (even length).
        # 5. Set the final node's next to None to terminate the list.
        # Time Complexity: O(N) — one pass to collect, one pass to interleave.
        # Space Complexity: O(N) — the array holds all N node references.
        if not head:
            return

        node_list = []
        cur = head
        while cur:
            node_list.append(cur)
            cur = cur.next

        l_idx, r_idx = 0, len(node_list) - 1
        while l_idx < r_idx:
            node_list[l_idx].next = node_list[r_idx]
            l_idx += 1

            if l_idx == r_idx:
                break

            node_list[r_idx].next = node_list[l_idx]
            r_idx -= 1

        node_list[l_idx].next = None

Solution 2:

class Solution:
    def reorderList(self, head: Optional[ListNode]) -> None:
        # Approach: Find Midpoint → Reverse Second Half → Merge
        # This breaks the problem into three well-known linked list primitives:
        #
        # Step 1 — Find the midpoint using slow/fast pointers (Floyd's technique).
        #   slow moves one step, fast moves two. When fast hits the end, slow is at the mid.
        #
        # Step 2 — Split the list at mid. Cut idx1.next = None, keep the second half in idx2.
        #   Reverse the second half in place (same as LeetCode 206).
        #
        # Step 3 — Interleave the two halves: pick one node from the front half,
        #   then one from the reversed back half, alternating until one side is exhausted.
        #
        # Time Complexity: O(N) — three linear passes.
        # Space Complexity: O(1) — all wiring done in place, no extra storage.
        idx1 = head
        idx2 = head

        # Step 1: find midpoint
        while idx2 and idx2.next:
            idx1 = idx1.next
            idx2 = idx2.next.next

        # Step 2: split and reverse the second half
        idx2 = idx1.next
        idx1.next = None
        idx1 = head

        pre = None
        cur = idx2
        while cur:
            tmp = cur.next
            cur.next = pre
            pre = cur
            cur = tmp

        # Step 3: merge the two halves
        while idx1 and pre:
            idx1_tmp = idx1.next
            pre_tmp = pre.next

            idx1.next = pre
            pre.next = idx1_tmp

            idx1 = idx1_tmp
            pre = pre_tmp

Conclusion

Today we reordered a linked list into the interleaved pattern L0→Ln→L1→Ln-1→…

Solution 1 is the intuitive approach: dump all nodes into an array, then use two pointers to weave them together from both ends. The array gives us O(1) random access to any node, so the interleaving is straightforward. The tradeoff is O(N) extra space.

Solution 2 achieves O(1) space by decomposing the problem into three primitives we've already seen:

1. Find the midpoint — slow/fast pointers from LeetCode 141.
2. Reverse the second half — in-place reversal from LeetCode 206.
3. Merge the two halves — alternating one node from each until one side runs out.

Each step is a single linear pass. The only subtle detail in Step 3 is saving both idx1.next and pre.next before rewiring — otherwise we lose our place in one of the halves.

This three-step pattern is a classic linked list technique that shows up across many problems. Recognizing that a complex reordering can be broken into known primitives is the key insight here.