A-037● Day 372026.06.12mediumleetcode #143neetcode150

Reorder List

#linked-list#two-pointers#stack#recursion

Problem

· problem

P.037

Reorder List

You are given the head of a singly linked-list. The list can be represented as: L₀ → L₁ → … → Lₙ₋₁ → Lₙ Reorder the list to be on the following form: L₀ → Lₙ → L₁ → Lₙ₋₁ → L₂ → Lₙ₋₂ → … You may not modify the values in the list's nodes. Only nodes themselves may be changed.

constraints

· 1 ≤ number of nodes ≤ 5 × 10⁴
· 1 ≤ Node.val ≤ 1000

// paraphrased summary — see source for full text

examples

example 1input → output

[1,2,3,4]

[1,4,2,3]

example 2input → output

[1,2,3,4,5]

[1,5,2,4,3]

Pre-solve

· pre-solve

● 1list shown→● 2select→● 3reveal

☐
Can we modify node pointers?
☐
What if the list has only one node?
☐
When the list has odd length, where does the middle node end up?
☐
Do we need to use additional data structures like stacks or queues?
☐
How can we find the middle of the list?
☐
Should we create new ListNode objects?
☐
Is using a hash map to store node values efficient?

check the items you would ask, then press confirm

// session-only state — refresh resets (repeatable practice)

Logic Structure

· logic

● 1slots shown→● 2pick per slot→● 3reveal

// pick one code line per slot to assemble the algorithm flow. no typing — just the logic skeleton.

step 1· Initialize pointers

○

slow, fast = head, head.next

○

slow, fast = head, head

○

slow, fast = head.next, head

step 2· Find middle of list│ nested

○

while fast and fast.next:

○

while fast:

○

while fast and fast.next and fast.next.next:

step 3· Separate list halves

○

second = slow.next

○

second = slow

○

second = slow.next.next

step 4· Cut list at middle

○

prev = slow.next = None

○

prev = None

step 5· Reverse second half│ nested

○

while second:

○

while second.next:

step 6· Merge two halves│ nested

○

while second:

○

while first:

○

first.next = second; first = second

pick one option per slot

// format: slot — recursive / DP patterns use ordering / state-first formats. ADR-08 follow-up.

Solve · Trace

· solve

solution.py

class Solution:

    def reorderList(self, head: ListNode) -> None:

        # find middle

        slow, fast = head, head.next

        while fast and fast.next:

            slow = slow.next

            fast = fast.next.next

        # reverse second half

        second = slow.next

        prev = slow.next = None

        while second:

            tmp = second.next

            second.next = prev

            prev = second

            second = tmp

        # merge two halfs

        first, second = head, prev

        while second:

            tmp1, tmp2 = first.next, second.next

            first.next = second

            second.next = tmp1

            first, second = tmp1, tmp2

mental dry-run cases

// walk each case in your head; expand the worked example below if stuck.

case 1

[1,2,3,4]

→

[1,4,2,3]

case 2

[1,2,3,4,5]

→

[1,5,2,4,3]

// UI does not walk-through — you do the dry-run mentally. Expand the worked example if stuck.