LeetEye LeetEye
Medium Linked List ~5 min

Reorder List

linked-list reorder-list

Problem

You are given the head of a singly linked list. The list can be represented as:
``
L0 → L1 → L2 → ... → Ln-1 → Ln
`

Reorder the list to be in the following form:
`
L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → ...
``

You may not modify the values in the list's nodes. Only nodes themselves may be changed.

Examples

Example 1
Input: head = [1,2,3,4]
Output: [1,4,2,3]
Example 2
Input: head = [1,2,3,4,5]
Output: [1,5,2,4,3]
Key Insight

Three steps: find middle with slow/fast, reverse second half, merge alternately.

Find middle, reverse second half, merge alternately. Three fundamental operations combined.

How to Approach This Problem

Pattern Recognition: When you see keywords like reorder list linked-list, think Linked List.

Step-by-Step Reasoning

1 To access nodes from the end, we need to:
Answer: Reverse just the second half
We need first half forward, second half backward. Reverse only second half.
2 To find the middle of a linked list efficiently:
Answer: Use fast and slow pointers
When fast reaches end, slow is at middle. O(n) time, O(1) space.
3 For [1,2,3,4,5], the middle element (3) should:
Answer: Go in the first half
After merge, order is 1,5,2,4,3. The middle element ends up at the end of the result.
4 When merging [1,2,3] and [5,4], we alternate:
Answer: 1 from first, 1 from second, repeat
The pattern is L0, Ln, L1, Ln-1, ... — alternating from front and back.
5 We stop merging when:
Answer: Second half is exhausted
Second half is equal or shorter. When it's done, first half might have one node left (the original middle).
6 This problem should be solved in:
Answer: O(1) space
All three steps (find middle, reverse, merge) can be done in-place with O(1) extra space.

Solution

def reorderList(head: ListNode) -> None:
    if not head or not head.next:
        return
    
    # 1. Find middle with slow/fast
    slow = fast = head
    while fast.next and fast.next.next:
        slow = slow.next
        fast = fast.next.next
    
    # 2. Reverse second half
    prev, curr = None, slow.next
    slow.next = None  # Cut the list
    while curr:
        next_temp = curr.next
        curr.next = prev
        prev = curr
        curr = next_temp
    
    # 3. Merge two halves alternately
    first, second = head, prev
    while second:
        tmp1, tmp2 = first.next, second.next
        first.next = second
        second.next = tmp1
        first, second = tmp1, tmp2

Complexity Analysis

Time O(n)
Space O(1)

Master This Pattern

Build intuition with interactive MCQs. Practice Linked List problems in the LeetEye app.

Download LeetEye Free
Practice in LeetEye