DSA sheet · Linked List · Merge & sort pattern

Partition List

This problem sits in the merge & sort part of the linked list sheet, and the teacher calls it a very common interview question. We must rearrange a list so that all the small values come first, while keeping the original order inside each group. She first solves it the "array way" (copy values out, arrange them, write them back), then shows the proper linked list way: split the nodes into two chains with two dummy nodes, then join the chains. The second idea, "build two lists side by side and glue them", shows up again and again in linked list problems.

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 list basics you need here (node, walking, dummy node, tail pointer)
• Part A · Brute force: copy values into a list, then overwrite
• Part B · Optimal: two dummy nodes, small chain + large chain
• Part C · Revision page

Part 0 · Before starting

What is a linked list node?

A linked list is a chain of small boxes called nodes. Each node holds two things: a value (val) and a link to the next box (next). The last node's next is None, which means "the chain ends here". The first node is called the head. If we only have the head, we can still reach every node by following the links.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val      # the number stored in this box
        self.next = next    # the next box, or None at the end

head
 ↓
[1] → [4] → [3] → [2] → [5] → [2] → None

Walking through a list

We keep a pointer (a variable that refers to a node), usually called curr. We start at the head and move with curr = curr.next until curr becomes None.

curr = head
while curr is not None:
    print(curr.val)      # do something with this node
    curr = curr.next     # step to the next box

No index access. In an array, arr[4] jumps straight to position 4. A linked list has no such jump. To reach position i you must walk i steps from the head, which costs O(n). That's why linked list solutions are built around walking forward once.

Save next before you change a pointer

A node's next is the only road to the rest of the list. If you overwrite node.next and haven't kept the old value somewhere, the rest of the chain is lost. In this problem we stay safe in a different way: we change small.next or large.next (the end of a chain we are building), and we keep our walking pointer curr moving along the original links.

The dummy node

A dummy node is a fake node, for example ListNode(0), that we put in front of a list we are building. Its value never matters. Why use it?

• When we build a new chain, the very first node is a special case: "is the chain still empty? then this node becomes the head". With a dummy in front, the chain is never empty. We always attach to the end, the same way, every time.
• At the end, the real head is simply dummy.next.

The tail pointer (and why we need a second name for it)

To add nodes at the end of a chain quickly, we keep a pointer to the last node of that chain, called the tail. To add a node: tail.next = node, then tail = tail.next. If we used the dummy itself as the moving pointer, it would drift to the end and we would lose the start of the chain. So we keep two names: the dummy stays still (it remembers the start), and a copy of it moves (it remembers the end).

[0] → [1] → [2] → [2]
 ↑                 ↑
small_dummy       small     (dummy stays, small moves)

Part A · Brute force: copy the values, arrange, write back

LeetCode 86 · Partition List

1The question in simple words

You get the head of a linked list and a number x. Rearrange it so that every node with value less than x comes before every node with value greater than or equal to x. Inside each group, the nodes must stay in the same order as in the original list.

input   x = 3
[1] → [4] → [3] → [2] → [5] → [2] → None

small ( < 3 ):  1, 2, 2        (in original order)
large (>= 3 ):  4, 3, 5        (in original order)

output
[1] → [2] → [2] → [4] → [3] → [5] → None

The teacher goes through it node by node: 1 is smaller than 3 → left side. 4 is bigger → right side. 3 is equal to x → it counts as "greater than or equal", so right side. 2 → left. 5 → right. 2 → left.

2What the constraints tell us

• Number of nodes: 0 to 200 → 0 is allowed, so the list can be empty. In the brute force we add a base case: if head is None, return None.
• n ≤ 200 is tiny. The teacher's usual rule: around 10⁸ operations is the edge, and 10⁹ surely gives TLE. Walking the list a few times is only a few hundred steps, so it's totally safe. (She also adds that for linked lists we don't write quadratic solutions anyway.)
• Values: −100 to 100 → very small, a normal int is fine (no long needed). In Python ints never overflow, but she always checks this.

3Intuition: pretend it's an array

Forget the links for a moment and picture the values in a normal Python list: [1, 4, 3, 2, 5, 2]. Arranging them is easy. The teacher gives two ways:

• Way 1: two lists. Walk once. Put values < x into a "left" list, values ≥ x into a "right" list. Then join them: [1, 2, 2] + [4, 3, 5].
• Way 2: one list, two passes. First pass: add only the values < x → [1, 2, 2]. Second pass: add only the values ≥ x → [1, 2, 2, 4, 3, 5].

Both keep the original order inside each group, because we read the values left to right. Once we have the arranged values, we walk the linked list one more time and overwrite each node's value with the next value from our arranged list.

4Building the logic

The linked list part is just "read the values" and "write the values back":

1. Read: walk with curr, and collect values that are < x.
2. Read again: walk from the head again, and collect values that are ≥ x.
3. Write: walk from the head a third time with an index i. Set curr.val = values[i], then move both.

5Approach steps

1. If the list is empty, return None.
2. Walk the list, add every value < x to values.
3. Walk again, add every value ≥ x to values.
4. Walk a third time, writing values[0], values[1], … into the nodes.
5. Return head (same nodes, new values).

6Code (Python)

class Solution:
    def partition(self, head, x):
        if head is None:                 # 0 nodes allowed
            return None

        values = []
        curr = head
        while curr is not None:          # pass 1: the small values
            if curr.val < x:
                values.append(curr.val)
            curr = curr.next

        curr = head
        while curr is not None:          # pass 2: the large values
            if curr.val >= x:
                values.append(curr.val)
            curr = curr.next

        curr = head
        i = 0
        while curr is not None:          # pass 3: write them back
            curr.val = values[i]
            i += 1
            curr = curr.next
        return head

7Code line by line

8Dry run (x = 3)

9Complexity & remember

• Time O(3n) = O(n): three full walks. With n = 200 that's about 600 steps, totally safe.
• Space O(n) extra for values. The teacher counts it as about 2n: n for the values list, plus the list we hand back as the answer (she counts the returned list too).

Part B · Optimal: two dummy nodes (small chain + large chain)

1The question (same as Part A), with a new rule

Same input, same output. But now we are not allowed to store values anywhere. We have to work with the nodes themselves and change only the next links.

2What the constraints tell us

• 0 nodes allowed → our code must return None for an empty list. (With dummy nodes this happens on its own; see step 4.)
• n ≤ 200 → one walk is clearly fast enough. The goal here is not speed, it's doing it without an array.

3Intuition: two queues at a counter

Picture people walking past a counter one by one. Each person is sent to one of two lines: the "small" line or the "large" line. Each new person joins the end of their line, so each line keeps the arrival order. When everyone has passed, the small line is followed by the large line.

That's exactly the plan. One pointer can't look after two groups at once, so the teacher says we need two chains: one for nodes < x, one for nodes ≥ x. At the end, we connect the last node of the small chain to the first node of the large chain.

4Building the logic, the way the teacher derives it

Step 1: where do the two chains start? → two dummy nodes

The first node we meet (1) must be attached somewhere. Attaching to "the next of small" means small must already be a node. So we make two fake nodes with value 0: small_dummy and large_dummy.

small_dummy → [0] → None
large_dummy → [0] → None

Step 2: attach the node to the right chain

Walk with curr. If curr.val < x, attach it to the small chain. Otherwise (≥ x), attach it to the large chain.

Step 3: why we need moving pointers small and large

The teacher's first thought is to write small_dummy.next = curr. That works for the first node. But the next small node must go after 1, not after the dummy. If we moved small_dummy forward to make room, we would no longer know where the chain starts, and we could never read it from the beginning again.

Her fix: keep the dummy still, and make a separate alias that moves, just like we use curr to walk without moving head. So: small = small_dummy and large = large_dummy. These are the tail pointers of the two chains.

Step 4: always move curr

Whether the if-branch or the else-branch ran, we are done with this node, so after the if/else we always do curr = curr.next. The loop runs while curr is not None.

Step 5: after the loop, join the chains

Now we have two separate chains: 0 → 1 → 2 → 2 and 0 → 4 → 3 → 5. The last small node (where small stands) must point to the first real large node. We don't have a variable on 4, but we know it is large_dummy.next:

Step 6: cut the end of the large chain → large.next = None

This is the line the teacher adds while coding, and it's the one most people forget. Node 5 was originally followed by the last 2. We never changed 5.next, so it still points to that 2. But that 2 is now inside the small chain, which leads back to 4 … 5 … 2 … forever. That's a cycle.

without large.next = None:

[1] → [2] → [2] → [4] → [3] → [5]
              ↑                 │
              └─────────────────┘   5 still points to the old last 2 → endless loop

So after joining we set large.next = None. Now the list really ends after 5.

Step 7: what do we return?

Reading from small_dummy gives 0 → 1 → 2 → 2 → 4 → 3 → 5. The 0 is our fake node, not part of the answer. The real head is small_dummy.next.

5Approach steps

1. Make small_dummy and large_dummy. Set tails small, large to them.
2. Walk curr from head to None.
3. If curr.val < x: attach to small and move small. Else: attach to large and move large.
4. Move curr.
5. After the loop: small.next = large_dummy.next, then large.next = None.
6. Return small_dummy.next.

6Code (Python)

class Solution:
    def partition(self, head, x):
        small_dummy = ListNode(0)        # start of the "< x" chain
        large_dummy = ListNode(0)        # start of the ">= x" chain
        small = small_dummy              # tail of the small chain (moves)
        large = large_dummy              # tail of the large chain (moves)

        curr = head
        while curr is not None:
            if curr.val < x:
                small.next = curr        # attach to the small chain
                small = small.next
            else:
                large.next = curr        # attach to the large chain
                large = large.next
            curr = curr.next             # always move on

        small.next = large_dummy.next    # join: small chain → large chain
        large.next = None                # cut the old link (avoids a cycle)
        return small_dummy.next

7Code line by line

8Dry run (x = 3, list 1 → 4 → 3 → 2 → 5 → 2)

I'll name the two 2s as 2a (4th node) and 2b (6th node), so we can track them. S = small_dummy, L = large_dummy.

Snapshot after step 4:

S → [0] → [1] → [2a]                L → [0] → [4] → [3]
                  ↑                                  ↑
                small                              large
curr is on [5]   (curr moves along the ORIGINAL links: 2a.next was 5)

Snapshot after the loop, before joining:

S → [0] → [1] → [2a] → [2b]         L → [0] → [4] → [3] → [5] ─→ (old link to 2b)
                         ↑                                  ↑
                       small                              large

Final, after join and cut, returning S.next:

[1] → [2] → [2] → [4] → [3] → [5] → None

9Complexity & remember

• Time O(n): one single walk, we never restart. The brute force did 3 walks (3n). The teacher stresses that in linked lists, going from 3n to n (or from 2n space to n space) counts as a real optimisation, even though both are "linear".
• Space O(1) extra: only two dummy nodes and a few pointers. We reused the original nodes. The teacher describes it as O(n) because she counts the list we return, and compares it to about 2n for the brute force (array + returned list). Either way, this version adds no array, which is what makes it the accepted in-place answer.

Part C · Revision page

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

def to_list(head):
    out = []
    while head:
        out.append(head.val)
        head = head.next
    return out

s = Solution()
print(to_list(s.partition(build([1, 4, 3, 2, 5, 2]), 3)))   # [1, 2, 2, 4, 3, 5]
print(to_list(s.partition(build([2, 1]), 2)))               # [1, 2]
print(to_list(s.partition(build([]), 0)))                   # []

Based on this video: Partition List