MEDIUM

Reorder List

Given the head of a singly linked list, reorder it in place to interleave the first half with the reversed second half: L0 → Ln → L1 → Ln-1 → L2 → … You must do this by rewiring nodes, not by swapping values.

Example

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

Output [1,4,2,3]

Key Pointers

Break it into three already-solved subproblems: find the middle, reverse the second half, then merge the two halves alternately.
Splitting at the middle turns a hard "reorder" problem into two familiar patterns strung together.
When merging, alternate one node from each half — the first half may have exactly one extra node when the length is odd.

Step-by-Step Analysis

Find the middle of the list with slow/fast pointers.
Split the list at the midpoint and reverse the second half.
Merge the two halves by alternating nodes: one from the first half, one from the reversed second half, repeat.
Set the final node's next to None to terminate the list cleanly.

Complexity

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

Code

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reorderList(head: ListNode) -> None:
    slow, fast = head, head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    second = slow.next
    slow.next = None
    prev = None
    while second:
        nxt = second.next
        second.next = prev
        prev = second
        second = nxt
    second = prev

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

Code Explanation

How the solution above works, piece by piece.

Phase 1: slow moves 1 step and fast 2 steps; when fast reaches the end, slow is at the middle.
Phase 2: second = slow.next, then slow.next = None splits the list in two. The second half is reversed with the usual prev/curr loop.
Phase 3: weave. Save first.next and second.next in tmp1, tmp2, link first → second → tmp1, then advance both.
The loop runs while second has nodes. The first half is never shorter than the second, so once second runs out, the first half's remaining nodes are already linked in order.
Everything is done by relinking in place: O(n) time, O(1) extra space.

Visual Walkthrough

Running it on head = [1, 2, 3, 4]:

The answer takes nodes alternately from the front and the back. Reversing the second half turns "from the back" into a simple forward walk, so the two halves can be merged like a zipper.

first halfsecond half

Video Explanation

NeetCode — LinkedIn Interview Question, LeetCode 143