DSA sheet · Linked List · Merge & sort pattern

Reorder List

This problem is in the merge / sort pattern, but the teacher's real lesson is that one problem can need several patterns at once. The optimal answer uses fast & slow pointers (find the middle), reversal (turn the second half around) and a merge (weave the two halves together). She gets there in three steps: (A) copy the values into an array and use two pointers, (B) store the nodes in an array so we really rewire arrows, and (C) drop the array completely.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · Linked lists, fast/slow and reversal from scratch
• Part A · Brute force 1: values in an array, two pointers, write back
• Part B · Brute force 2: nodes in an array, rewire with two pointers
• Part C · Optimal: middle → reverse second half → weave
• Part D · Revision page

Part 0 · Before starting

Nodes, head, None

A linked list is a chain of nodes. Each node has a value (val) and an arrow to the next node (next). The last node points to None. The first node is the head.

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

[1] → [2] → [3] → [4] → None
 ↑
head

Walking, and no index

You can't say "give me node 3". You start at head and follow arrows with curr = curr.next, so reaching position i takes O(i) steps. Walk with a helper (curr), never with head, or you lose the start of the list.

Also: arrows only go forward. From node 4 there is no way back to node 3. That single fact is why this problem is harder on a list than on an array.

Save next before you change it

A node knows only its next node. If you overwrite a.next and nobody else points to the old next node, that node and everything after it are lost. In this problem we save two nexts before rewiring (called next1 and next2 below).

Fast & slow pointers: finding the middle

Start two pointers at head. Each round, slow moves 1 step and fast moves 2 steps. When fast reaches the end, slow has covered half the distance, so it's in the middle.

slow = fast = head
while fast is not None and fast.next is not None:
    slow = slow.next
    fast = fast.next.next
# slow is the middle

[1] → [2] → [3] → [4] → [5] → None
             ↑           ↑
            slow        fast (fast.next is None → stop)
slow = 3, the exact middle

[1] → [2] → [3] → [4] → None
             ↑            ↑
            slow         fast = None → stop
slow = 3, the 2nd of the two middles

The loop needs both checks: fast is not None (even length ends with fast on None) and fast.next is not None (odd length ends with fast on the last node; jumping two from there would crash).

Reversal with prev / curr / nxt

prev = None
curr = start
while curr is not None:
    nxt = curr.next      # save the way forward
    curr.next = prev     # turn the arrow around
    prev = curr          # prev steps forward
    curr = nxt           # curr steps forward
# prev is the new head of the reversed part

before:  [3] → [4] → None        after:  None ← [3] ← [4]
          ↑                                            ↑
        start                                     prev (new head)

Because prev starts at None, the old first node (3) ends up pointing to None. We will use that fact.

Part A · Brute force 1: values in an array

LeetCode 143 · Reorder List

1The question in simple words

Given a list L0 → L1 → … → Ln, rearrange it to first, last, second, second-last, third, third-last…

L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …

before: [1] → [2] → [3] → [4]
after:  [1] → [4] → [2] → [3] → None

before: [1] → [2] → [3] → [4] → [5]
after:  [1] → [5] → [2] → [4] → [3] → None

You must change the list in place. The function returns nothing (LeetCode's signature returns None); the caller still holds the head, which stays node 1.

2What the constraints tell us

• Number of nodes: 1 to 5 × 10⁴ (the teacher reads it as up to 10⁴; either way) → at least 1, so head is never None. No null check for head itself.
• O(n²) is rarely needed for lists; brute force and optimal are both linear here. The difference is extra space and number of passes.

3Intuition: if it were an array

The teacher first lists the patterns we know so far (basics, fast/slow, reversal, merge/sort) and says: suppose we didn't know any of them. With an array, "first, last, second, second-last" is exactly two pointers: left at the start, right at the end.

[1, 2, 3, 4]
 L        R     take 1, take 4 → L+1, R-1
    L  R        take 2, take 3 → L+1, R-1
    R  L        crossed → stop        result: 1 4 2 3

4Building the logic

Copy every value into an array. Build the new order with two pointers (left value, right value, move both inward, stop when they cross; if they land on the same index, take it once). Then walk the list again and overwrite the values in that order.

5Approach steps

1. Copy values into vals.
2. left = 0, right = n − 1; while left ≤ right: add vals[left]; if left ≠ right add vals[right]; left += 1, right −= 1.
3. Overwrite the nodes with the new order.

6Code (Python)

class Solution:
    def reorderList(self, head):
        vals = []
        curr = head
        while curr is not None:          # copy values out
            vals.append(curr.val)
            curr = curr.next

        order = []
        left, right = 0, len(vals) - 1
        while left <= right:             # first, last, second, second-last...
            order.append(vals[left])
            if left != right:            # middle of an odd list: add it once
                order.append(vals[right])
            left += 1
            right -= 1

        curr = head
        for v in order:                  # write values back
            curr.val = v
            curr = curr.next

7Code line by line

8Dry run: 1 → 2 → 3 → 4

9Complexity & remember

• Time: n (copy) + n/2 (two pointers) + n (write back) = 5n/2 → O(n).
• Space O(n).

Part B · Brute force 2: nodes in an array, rewire arrows

1The question in simple words

Same task, but now we obey the statement: we change the arrows, not the values. The trick is to store the node objects in the array, not their numbers.

2What the constraints tell us

• At least 1 node. With 1 node or 2 nodes the answer equals the input (1 → 2 is already "first, last"), so the teacher returns early when head.next is None or head.next.next is None.

3Intuition: an array gives us backward steps

The list can't walk backward, but an array can: arr[right] is the last node, arr[right-1] the one before it. Storing a node in the array is cheap: it's just a reference to the box, not a copy of the whole chain.

index:  0     1     2     3
arr:   [n1]  [n2]  [n3]  [n4]      (n1 is the node with value 1, …)
        L                 R

4Building the logic, one arrow at a time

Arrow 1: left points to right

arr[left].next = arr[right] → 1 now points to 4 (its old arrow to 2 is erased).

Move left before the next arrow

Now 4 must point to 2. 2 is arr[left + 1], so we do left += 1 first, then connect.

Arrow 2: right points to the new left

arr[right].next = arr[left] → 4 points to 2. Then right -= 1.

Why a break in the middle: left == right

The loop runs while left < right. Between "left += 1" and arrow 2 we check if left == right: break. Why?

• Even length (1 2 3 4): round 2 sets 2 → 3, then left moves to 3, the same index as right. Connecting 3 → 3 would make a self-loop. Nothing left to connect → break.
• Odd length: the teacher's observation is that with odd length the two pointers always meet on the same index before they could cross; with even length they would jump past each other if both moved together. Moving one at a time and checking in between catches the meeting point in both cases.

After the loop: cut the tail

Read from the head now: 1 → 4 → 2 → 3 → … and 3 still points to 4 (its old arrow). So the list goes 1 4 2 3 4 2 3 4 … forever. The node at arr[left] is the new last node, so set arr[left].next = None.

5Approach steps

1. If 1 or 2 nodes → return.
2. Put every node in arr.
3. left = 0, right = n − 1. While left < right:
4. arr[left].next = arr[right]; left += 1.
5. If left == right → break.
6. arr[right].next = arr[left]; right -= 1.
7. After the loop: arr[left].next = None.

6Code (Python)

class Solution:
    def reorderList(self, head):
        if head.next is None or head.next.next is None:   # 1 or 2 nodes
            return

        arr = []
        curr = head
        while curr is not None:          # store the NODES, not values
            arr.append(curr)
            curr = curr.next

        left, right = 0, len(arr) - 1
        while left < right:
            arr[left].next = arr[right]  # first -> last
            left += 1
            if left == right:            # pointers met: nothing more to link
                break
            arr[right].next = arr[left]  # last -> second
            right -= 1

        arr[left].next = None            # new tail, cuts the old arrow (no loop)

7Code line by line

8Dry run: 1 → 2 → 3 → 4 → 5

Even case 1 2 3 4: step 1 links 1 → 4, left 1; 4 → 2, right 2; step 2 links 2 → 3, left 2 = right → break; then 3.next = None → 1 → 4 → 2 → 3.

9Complexity & remember

• Time: n (fill) + n/2 (rewire) = 3n/2 → O(n). Better than 5n/2.
• Space O(n): the array of nodes. Still brute force.

Part C · Optimal: middle → reverse → weave

O(1) extra space

1The question in simple words

Same reorder, no array at all.

2What the constraints tell us

• Same early return for 1 or 2 nodes.
• We need the "walk backward from the end" ability of the array, without the array.

3Intuition: make the right pointer able to walk left

The teacher links this to Palindrome Linked List: there too we compared first with last, second with second-last. On a list, right -= 1 is impossible because the arrows point right. But if the second half were reversed, its arrows would point left, and right = right.next would walk from the end toward the middle.

reverse the second half:

[1] → [2] → [3] ← [4]        reading from 4: 4 → 3 → None
 ↑                 ↑
left             right       left = left.next, right = right.next
                             both now walk toward the middle

How much do we reverse? Left and right meet in the middle, and anything past that is not needed, so only the second half. To find the middle we use fast & slow. So the plan is three patterns in a row:

1. Fast & slow → find the middle node.
2. Reversal → reverse from the middle to the end.
3. Merge (weave) → take one node from the front half, one from the reversed back half, and so on.

4Building the logic

Step 1 and 2: the two halves

With fast & slow starting at head, slow stops on node 3 for both 1 2 3 4 and 1 2 3 4 5. Reverse from slow to the end. Since the reversal's prev starts at None, the middle node ends up pointing to None.

first:  [1] → [2] → [3] → None
second: [4] → [3]            (same node 3!)
2 still points to 3

first:  [1] → [2] → [3] → None
second: [5] → [4] → [3]      (same node 3)

Both halves end at the same middle node, and the middle node points to None. Keep that in mind for the stop condition.

Step 3: weave, saving two nexts

Call the pointers first (front half, starts at head) and second (reversed back half, starts at prev). One round:

• 1 must point to 4. But 1's current arrow leads to 2, which we still need. So save it first: next1 = first.next. Then first.next = second.
• 4 must point to 2. But 4's current arrow leads to 3, which we still need. Save it: next2 = second.next. Then second.next = next1.
• "left++ and right−−" on a list means: first = next1, second = next2.

round 1 on 1 2 3 4:
before:   first=[1] → [2] → [3]       second=[4] → [3]
saves:    next1 = [2]                 next2 = [3]
after:    [1] → [4] → [2] → [3] → None
move:     first = [2], second = [3]

When to stop? (a fix to what's said on screen)

The teacher says to keep going "until second becomes None", because the reversed half always runs out first. Let's test that on 1 2 3 4 after round 1: first = 2, second = 3, and 2's arrow already goes to 3.

• next1 = 2.next = 3, next2 = 3.next = None.
• 2.next = 3 (fine), then 3.next = next1 = 3 → node 3 points to itself, an infinite loop.

What do we return?

Nothing. The task is to change the list in place; head is still node 1 and the caller already has it.

5Approach steps

1. If 1 or 2 nodes → return.
2. Fast & slow from head → slow is the middle.
3. Reverse from slow to the end → prev is the head of the reversed half.
4. first = head, second = prev.
5. While second.next is not None: save next1, next2; first.next = second; second.next = next1; first = next1; second = next2.

6Code (Python)

class Solution:
    def reorderList(self, head):
        if head.next is None or head.next.next is None:   # 1 or 2 nodes
            return

        # 1. find the middle (fast & slow)
        slow = fast = head
        while fast is not None and fast.next is not None:
            slow = slow.next
            fast = fast.next.next

        # 2. reverse from the middle to the end
        prev = None
        curr = slow
        while curr is not None:
            nxt = curr.next
            curr.next = prev
            prev = curr
            curr = nxt

        # 3. weave the two halves
        first, second = head, prev
        while second.next is not None:   # stop at the shared middle node
            next1 = first.next           # save the front half's way forward
            next2 = second.next          # save the back half's way forward
            first.next = second          # front -> back
            second.next = next1          # back -> next front
            first = next1                # "left++"
            second = next2               # "right--"

7Code line by line

8Dry run: 1 → 2 → 3 → 4 → 5

[1] → [2] → [3] → None
             ↑
[5] → [4] ───┘
 ↑
first = [1], second = [5]

[1] → [5] → [2] → [3] → None
                   ↑
            [4] ───┘
first = [2], second = [4]

[1] → [5] → [2] → [4] → [3] → None
                         ↑
               first = second = [3]
               second.next None → stop

Even case 1 2 3 4: after round 1 the list is 1 → 4 → 2 → 3 → None, first = 2, second = 3, and 3.next is None → stop. Correct, with no self-loop.

9Complexity & remember

• Time: n/2 (middle) + n/2 (reverse half) + n/2 (weave) = 3n/2 → O(n).
• Space O(1): only pointers. That's what makes this the optimal answer.

Part D · Revision page

def build(vals):
    dummy = ListNode()
    tail = dummy
    for v in vals:
        tail.next = ListNode(v)
        tail = tail.next
    return dummy.next

def to_list(head, limit=100):
    out = []
    while head and len(out) < limit:   # limit guards against a loop
        out.append(head.val)
        head = head.next
    return out

s = Solution()
for vals in ([1, 2, 3, 4], [1, 2, 3, 4, 5], [1], [1, 2], [1, 2, 3]):
    h = build(vals)
    s.reorderList(h)
    print(to_list(h))
# [1, 4, 2, 3]  [1, 5, 2, 4, 3]  [1]  [1, 2]  [1, 3, 2]

Based on this video: Reorder List