DSA With AI
Week 3 ยท Linked List

Reorder List

Reorder L0 -> L1 -> ... -> Ln into L0 -> Ln -> L1 -> Ln-1... The runner returns reordered values.

Medium Linked List Week 3 Practice runner

Frame the problem

  • The LeetCode version mutates in place.
  • Odd-length lists keep the middle node last.
  • Avoid creating cycles while relinking.
1. Reveal example inputs and outputs

Example 1

Input:

reorder_list_values([
  1,
  2,
  3,
  4
])

Output:

[
  1,
  4,
  2,
  3
]

Example 2

Input:

reorder_list_values([
  1,
  2,
  3,
  4,
  5
])

Output:

[
  1,
  5,
  2,
  4,
  3
]
2. Brute force first

How would a deque make this easy? Which pointer operations remove that extra structure?

3. Reveal the insight ladder
  1. Find the middle with slow/fast pointers.
  2. Reverse the second half.
  3. Merge first and reversed second halves alternately.
  4. Terminate the final tail.
4. Dry run before code
  1. 1 -> 2 -> 3 -> 4 -> 5.
  2. Split to 1 -> 2 -> 3 and 4 -> 5.
  3. Reverse second half to 5 -> 4.
  4. Merge to 1 -> 5 -> 2 -> 4 -> 3.
5. Reveal final Python solution 
def reorder_list_values(values):
    result = []
    left, right = 0, len(values) - 1
    while left <= right:
        if left == right:
            result.append(values[left])
        else:
            result.extend([values[left], values[right]])
        left += 1
        right -= 1
    return result

Complexity: Pointer version: time O(n), space O(1). Browser value-list version builds O(n) output.

Interview narration

  • This combines find-middle, reverse, and merge.
  • Reversing the second half gives access to Ln, Ln-1, and so on.
  • Alternating links creates the requested order.

Common traps

  • Not cutting the list before reversing.
  • Creating a cycle during merge.
  • Losing the odd middle node.

Follow-up drills

1. Why not use a stack?

A stack is simpler but O(n) extra space; the in-place linked-list solution is stronger.

2. Where do cycles appear?

Old next pointers can point back into the merged structure if the first half or final tail is not terminated.

Interactive runner

Write the required Python function. Your code runs locally in this browser. Hints reveal one failing case at a time.