Reorder List (LeetCode 143)

The problem

You get the head of a singly linked list L0 -> L1 -> … -> Ln. Rearrange it in place into L0 -> Ln -> L1 -> Ln-1 -> L2 -> …. You must relink the nodes, not just swap their values.

Input:  1 -> 2 -> 3 -> 4 -> 5
Output: 1 -> 5 -> 2 -> 4 -> 3

Take from the front, then the back, then the front again, until you meet in the middle.

How to think about it

Start with brute force. Copy the nodes into an array. Then use two indices, one from each end, and relink arr[i] -> arr[j] -> arr[i+1] -> …. That is O(n) time and O(n) space. It’s a solid first answer, and the follow-up is to do it in O(1) space.

Look at the output shape. The result alternates between the front half in order and the back half in reverse. With 1 2 3 4 5, the front half is 1 2 3, the back half reversed is 5 4, and weaving them gives 1 5 2 4 3.

The key insight: this is three small problems glued together. (1) Find the middle with fast and slow pointers. (2) Cut the list there and reverse the back half in place. (3) Merge the two lists by alternating nodes. Each piece is a standard linked-list move in O(n) time and O(1) space, so the whole thing is too.

Which pattern is this? Fast & slow pointers to split, then in-place reversal and merging. The tell is “the answer pairs the front of a list with its back”.

Approach

1. If the list is empty, return.
2. Move s one step and f two steps while f.next and f.next.next exist. s stops at the end of the front half (the first middle).
3. Set second = s.next, then cut the list with s.next = None.
4. Reverse second in place; prev becomes its new head.
5. Weave: with first on the front half and second on the reversed back half, link first -> second -> (old first.next), advance both, and repeat while second has nodes.

Solution

def reorder_list(head):
    if not head: return None
    s = f = head
    while f.next and f.next.next: s = s.next; f = f.next.next   # s = end of front half
    second = s.next; s.next = None; prev = None                  # cut into two lists
    while second: second.next, prev, second = prev, second, second.next   # reverse back half
    first = head; second = prev
    while second:                                                 # weave front and back
        first.next, first = second, first.next
        second.next, second = first, second.next
    return head
# reorder_list([1,2,3,4,5]) -> [1,5,2,4,3]

Dry run

On 1 -> 2 -> 3 -> 4 -> 5:

On the even list 1 2 3 4, the middle is node 2, the halves are 1 2 and 4 3, and the weave gives 1 4 2 3.

Complexity

• Time: O(n). Finding the middle, reversing half the list and weaving are each one linear pass.
• Space: O(1). Only pointer variables; no nodes are created.

Edge cases and pitfalls

• Empty list: returns immediately.
• One or two nodes: the front half holds everything (or the back half is one node), and the list comes out unchanged. On 1 the result is 1.
• Forgetting to cut (s.next = None) leaves the front half still linked into the back half, which creates a cycle after weaving.
• First vs second middle. This loop stops on the first middle, so the front half is never shorter than the back half. That’s why the weave can loop on second alone.
• Swapping values instead of nodes is not allowed by the problem, and interviewers will notice.

Related problems

• Palindrome Linked List (LeetCode 234): the same middle-and-reverse set-up, then a comparison.
• Reverse Linked List (LeetCode 206): the reversal step on its own.
• Merge Two Sorted Lists (LeetCode 21): merging two lists, chosen by value instead of alternating.