Partition and odd-even reordering in Python

Why it matters

Partitioning means splitting a collection into two groups and placing one group before the other. Quicksort does this to arrays. On a linked list the same idea shows up in interview questions, and the task teaches something a plain walk does not: how to move nodes from one place to another by changing next references, without creating any new nodes.

Odd-even reordering is the same kind of move, but the rule decides by position in the list instead of by value. Both tasks use one walk through the list and a few pointer changes. Earlier lessons in this module covered the list shape and reversal. This lesson only rearranges nodes that already exist.

Words you will need

• Node: one box in a linked list. It holds a value and a next reference.
• Reference: a name that leads to an object. In Python, node.next holds a reference to the next node. It does not hold a copy of that node.
• Head: the first node of a list. You keep it in a name so you can walk the list from the start.
• Chain: a list that is still being built. This lesson uses the word for the two lists you fill during the walk.
• Relative order: the order of items compared with each other. If the list is 1, 4, 3, the relative order of 4 and 3 is that 4 comes first. Keeping relative order means each group keeps its original sequence.
• Predicate: a yes-or-no test on a value, such as lambda v: v < 3. The function returns True or False. Type hints can describe it as Callable[[int], bool].
• None: Python's value for "no object". Reading an attribute through None, such as None.next, raises an AttributeError.
• Dummy node: a placeholder node placed in front of a chain, so the chain always has a node before its first real node. You never print the dummy.
• Dataclass: a class written with the @dataclass decorator. Python writes its setup code for you. Split(yes, no) below holds two chains, and you read them back as .yes and .no.

The idea in plain words

Imagine a line of people waiting at a desk. The clerk must serve everyone under 18 first, and then everyone else. The clerk does not want to change the order inside either group. The clerk walks down the line once. Each person who is under 18 is moved to a short line A. Each other person goes to a short line B. Both short lines keep the order in which people joined them. At the end the clerk attaches line B to the back of line A.

That is the whole method for partitioning a linked list:

1. Walk the list once from the head.
2. Move each node into one of two chains, depending on a test.
3. Join the end of the first chain to the start of the second chain.

Here is the walk on the list 1 -> 4 -> 3 -> 2 -> 5 -> 2 with the test v < 3.

The join then makes the last node of the first chain (the 2) point to the first node of the second chain (the 4). The result is 1 -> 2 -> 2 -> 4 -> 3 -> 5. Every value below 3 comes first, and within each group the values keep their original order: 1, 2, 2 and 4, 3, 5.

There is one detail the table hides. When node 1 moves into the first chain, its next reference must not stay pointed at node 4. If it did, the loop would walk from node 1 straight to node 4 and skip the rest of its moves. So the code saves cur.next in a name before it moves cur. The common mistakes section shows what happens when this step is missing.

Step 1: a chain that remembers its end

Adding to the end of a plain list means walking from the head every time. That makes each add cost more as the list grows. A chain avoids this by keeping a reference to its last node. It also keeps a dummy node in front, so an empty chain and a non-empty chain behave the same way.

class ListNode:
    def __init__(self, val: int, next: "ListNode | None" = None):
        self.val = val
        self.next = next
 
 
class Chain:
    """A list that keeps a reference to its last node."""
 
    def __init__(self):
        self._dummy = ListNode(0)
        self._last = self._dummy
 
    def add(self, node: ListNode) -> None:
        self._last.next = node
        node.next = None
        self._last = node
 
    @property
    def head(self) -> "ListNode | None":
        return self._dummy.next
 
    @property
    def last(self) -> ListNode:
        return self._last

Read add line by line. The current last node is pointed at the new node. The new node's next is set to None, because it is now the end of this chain. Then _last moves onto the new node. Each add does the same three steps, so it costs the same amount of work whether the chain has 3 nodes or 3 million nodes.

The line node.next = None matters. A node that moves into a chain still carries its old next reference, which points at the rest of the original list. Clearing it cuts that link. Without the cut, the end of the chain would keep pointing into the other chain, and the list could loop. The common mistakes section shows that loop.

The leading underscore in _dummy and _last is a naming convention. It tells the reader that code outside the class should not change those names. Python does not enforce it.

The dummy node is why head never needs a special case. If nothing was added, self._dummy.next is None, which is the correct empty list.

The @property decorator lets chain.head and chain.last read like plain attributes, while the code still runs a small function behind them.

Step 2: split by a test

Now the walk. The function takes a list and a test, and returns two chains. The test is a predicate, so the same code works for "less than x" and for "is even". In Python a function is a value, so you pass the test in as an argument, and a lambda makes a small one-line function on the spot.

@dataclass
class Split:
    yes: Chain
    no: Chain
 
 
def split(head: "ListNode | None", test: Callable[[int], bool]) -> Split:
    yes = Chain()
    no = Chain()
    cur = head
    while cur is not None:
        nxt = cur.next
        if test(cur.val):
            yes.add(cur)
        else:
            no.add(cur)
        cur = nxt
    return Split(yes, no)

The line nxt = cur.next comes first in the loop body, before add. The add call sets cur.next to None, so reading it afterwards would give None and end the loop after one node. Saving it first is the only thing that keeps the walk going.

Here is the first example, with the test lambda v: v < 3, split by hand:

input:           1 -> 4 -> 3 -> 2 -> 5 -> 2
below 3:         1 -> 2 -> 2
3 or more:       4 -> 3 -> 5

The Split dataclass gives both chains back at once. Nothing has been joined yet, so each chain still has its own head.

Step 3: join the two chains

Joining is one assignment, if the code knows where the first chain ends.

def join(first: Chain, second: Chain) -> "ListNode | None":
    first.last.next = second.head
    return first.head
 
 
def partition(head: "ListNode | None", x: int) -> "ListNode | None":
    s = split(head, lambda v: v < x)
    return join(s.yes, s.no)

first.last is the final node of the first chain. Its next is set to the head of the second chain. The function returns the head of the first chain, which is the head of the whole list.

The dummy node makes the two empty cases work without an if.

• If the first chain is empty, last is its dummy node. Setting dummy.next to the second chain's head makes the second chain the result, and head returns it.
• If the second chain is empty, its head is None. The end of the first chain gets next = None, which is already true, so nothing breaks.

Running partition on the example and on some edge cases gives this output. The labels and spacing come from the print calls in the full program below.

partition x=3:   1 -> 2 -> 2 -> 4 -> 3 -> 5
empty:           (empty)
one node:        9
all below:       1 -> 2
all at or above: 5 -> 4

The program calls show to print a list. It joins the values with -> and prints (empty) when the head is None.

def show(head: "ListNode | None") -> str:
    if head is None:
        return "(empty)"
    parts = []
    cur = head
    while cur is not None:
        parts.append(str(cur.val))
        cur = cur.next
    return " -> ".join(parts)

Worked example: a different test, the same code

The split and the join do not depend on the test. Replace v < x with v % 2 == 0 and you get "even values first".

def even_values_first(head: "ListNode | None") -> "ListNode | None":
    s = split(head, lambda v: v % 2 == 0)
    return join(s.yes, s.no)

On the list 5 -> 2 -> 7 -> 4 -> 9 -> 6 the output is:

even first:      2 -> 4 -> 6 -> 5 -> 7 -> 9

The even values, 2, 4 and 6, come first in their original order. The odd values, 5, 7 and 9, follow in their original order. Only the predicate changed. This is what it means to put the logic that varies in one small piece of code.

Odd-even reordering: the rule is position, not value

Now the rule changes. Count the nodes from 1 in the order they appear. The nodes in positions 1, 3, 5 and so on are the odd-position nodes. The nodes in positions 2, 4, 6 and so on are the even-position nodes. The task is to put all odd-position nodes first, in their original order, followed by all even-position nodes, also in their original order.

Python counts from 0, so the code calls the first node index 0, but the task statement counts positions from 1. The two views describe the same nodes. Position 1 is the first node, the one at index 0.

For the list 1 -> 2 -> 3 -> 4 -> 5, the odd positions hold 1, 3 and 5. The even positions hold 2 and 4. The result is 1 -> 3 -> 5 -> 2 -> 4.

The position rule can use the same two-chain idea, but it does not need the Chain class. The walk alternates between two nodes. One name moves along the odd positions and another moves along the even positions. The code links nodes in place.

def odd_even(head: "ListNode | None") -> "ListNode | None":
    if head is None or head.next is None:
        return head
    odd = head
    even = head.next
    even_head = even
    while even is not None and even.next is not None:
        odd.next = even.next
        odd = odd.next
        even.next = odd.next
        even = even.next
    odd.next = even_head
    return head

The first two lines handle the short cases. A list with no nodes, or with one node, is already in the right order. The early return also means the rest of the function can assume there are at least two nodes.

odd starts on the first node. even starts on the second node. even_head remembers where the even chain starts, because the loop will change odd.next and the head of the even chain must not be lost.

The loop moves both names forward by two positions each time. In odd.next = even.next, the odd node jumps over the even node so it points at the next odd node. Then odd moves onto that node. In even.next = odd.next, the even node jumps over the odd node so it points at the next even node. Then even moves onto that node.

Here is what happens to 1 -> 2 -> 3 -> 4 -> 5:

The last line of the function, odd.next = even_head, makes the join. odd now sits on the last odd-position node, so this line attaches the even chain behind it. The even chain's last node already ends in None, because the loop left it there.

Running the function on the examples from the code gives this output:

odd-even [1,2,3,4,5]:     1 -> 3 -> 5 -> 2 -> 4
odd-even [2,1,3,5,6,4,7]: 2 -> 3 -> 6 -> 7 -> 1 -> 5 -> 4
odd-even []:              (empty)
odd-even [9]:             9

Harder example: a seven-node list

The list 2 -> 1 -> 3 -> 5 -> 6 -> 4 -> 7 has seven nodes. Its odd positions hold 2, 3, 6 and 7 (positions 1, 3, 5 and 7). Its even positions hold 1, 5 and 4 (positions 2, 4 and 6). The result is 2 -> 3 -> 6 -> 7 -> 1 -> 5 -> 4.

Notice that the values are not sorted or grouped by size. The rule looks only at where a node sits. A value of 2 in position 1 is an odd-position node, even though it is even. A value of 7 in position 7 is also an odd-position node, even though it is odd.

The loop stops when even is None or when even.next is None. For a seven-node list, the even pointer reaches node 4 (position 6) and then its next is node 7, which is an odd-position node. The loop runs one more time and moves even to None. The join then uses the last odd node, which is node 7.

Checking your work against a simple version

Hand-traced examples catch most mistakes, but not all. A good habit is to write a slow, obvious version, then compare the two on many random inputs. The slow version for partitioning builds two Python lists with list comprehensions. The slow version for odd-even reordering uses slicing. A slice such as vals[0::2] takes every second value, starting at index 0. The fast version must give the same values.

The full program does this for 2,000 random lists of length 0 to 12, with values from 0 to 9. The random numbers come from a seeded generator, so the same lists are made on every run.

random partition checks: 2000 cases, 0 mismatches
random odd-even checks:  2000 cases, 0 mismatches

The check compares values only, not node identity. That is the right level for this lesson, because the rules are about values and their order. The check is cheap, and it finds mistakes in edge cases that a hand trace might skip, such as a list where every node goes to one side.

Full program

This program has the chain, the split, the join, the position rule, and the random checks. Run it with python3 partition.py. It prints the output shown in this lesson.

The output is:

partition x=3:   1 -> 2 -> 2 -> 4 -> 3 -> 5
empty:           (empty)
one node:        9
all below:       1 -> 2
all at or above: 5 -> 4
 
even first:      2 -> 4 -> 6 -> 5 -> 7 -> 9
 
odd-even [1,2,3,4,5]:     1 -> 3 -> 5 -> 2 -> 4
odd-even [2,1,3,5,6,4,7]: 2 -> 3 -> 6 -> 7 -> 1 -> 5 -> 4
odd-even []:              (empty)
odd-even [9]:             9
 
random partition checks: 2000 cases, 0 mismatches
random odd-even checks:  2000 cases, 0 mismatches

Common mistakes

Mistake 1: reading next after moving the node. This is the mistake the idea section warned about. In sketch form, the loop looks like this:

cur = head
while cur is not None:
    if cur.val < x:
        small.add(cur)      # clears cur.next
    else:
        large.add(cur)      # clears cur.next
    cur = cur.next          # now always None

Run on 1 -> 4 -> 3 -> 2 -> 5 -> 2 with x = 3, this version keeps only the first node in the first chain:

1

The loop ends after the first node, because the first node's next was cleared as it moved. The fix is the line nxt = cur.next before the if, and then cur = nxt at the end.

Mistake 2: adding a node without clearing its next. If add does not set node.next = None, the last node of each chain keeps pointing at its old neighbour. The chains then point into each other, and the walk never ends. The version below leaves out the clearing line:

class BadChain:
    def __init__(self):
        self._dummy = ListNode(0)
        self._last = self._dummy
 
    def add(self, node):
        self._last.next = node      # no node.next = None
        self._last = node

Joining the two chains and walking the first 12 values from the head gives:

1 -> 2 -> 2 -> 4 -> 3 -> 5 -> 2 -> 4 -> 3 -> 5 -> 2 -> 4 -> ...

The values repeat, which is the sign of a cycle. A cycle is a list that loops back on itself. Any loop that walks such a list until it sees None will run forever. Clearing next in add prevents this.

Mistake 3: testing even.next without checking that even is not None. In odd_even, the loop checks even is not None before it reads even.next. A version without that check fails on lists with an odd number of nodes, because the loop moves even to None at the end of its last pass.

while even.next is not None:   # wrong: even can already be None here
    odd.next = even.next
    odd = odd.next
    even.next = odd.next
    even = even.next

Running this on 1 -> 2 -> 3 -> 4 -> 5 gives this result. Python also prints a traceback, which lists the lines the program was on. The line numbers in your copy will differ.

AttributeError: 'NoneType' object has no attribute 'next'

The message names the problem: the program read .next from None. The fix is the check even is not None in the loop test, which the function above already has.

Mistake 4: forgetting the join. If partition returns small.head without calling join, the nodes in the large chain are no longer reachable from the returned head. A program that prints the result shows only the values below x. The fix is the join call, which links the end of the first chain to the head of the second.

Mistake 5: joining to odd with the wrong value. In odd_even, the join must use even_head, the saved start of the even chain. If the last line were odd.next = even, the value of even at that point is None, because the loop has finished. The result would drop every even-position node. Running that wrong version on 1 -> 2 -> 3 -> 4 -> 5 prints:

1 -> 3 -> 5

Practice

Exercise 1. Trace partition on 2 -> 6 -> 1 -> 7 -> 3 with x = 4. Write the two chains and the final list.

Show the answer

The values below 4 are 2, 1 and 3, in that order. The values at or above 4 are 6 and 7, in that order. The result is 2 -> 1 -> 3 -> 6 -> 7.

Exercise 2. What does partition return for 3 -> 1 -> 2 with x = 3?

Show the answer

The value 3 is not less than 3, so it goes to the second chain. The values 1 and 2 go to the first chain. The result is 1 -> 2 -> 3.

Exercise 3. Change the test in partition from v < x to v <= x. What does the function return for 1 -> 4 -> 3 -> 2 -> 5 -> 2 with x = 3?

Show the answer

The first chain now takes every value up to and including 3. The values 1, 3, 2 and 2 go first, in their original order. The second chain keeps 4 and 5. The result is 1 -> 3 -> 2 -> 2 -> 4 -> 5.

Exercise 4. What does odd_even return for 10 -> 20 -> 30 -> 40?

Show the answer

Odd positions hold 10 and 30. Even positions hold 20 and 40. The result is 10 -> 30 -> 20 -> 40.

Exercise 5. A student wrote this ending for odd_even. What is wrong with it, and what does it return for 1 -> 2 -> 3 -> 4 -> 5?

odd = head
even = head.next
while even is not None and even.next is not None:
    odd.next = even.next
    odd = odd.next
    even.next = odd.next
    even = even.next
odd.next = even
return head

Show the answer

The last line joins odd to even, but even is no longer the start of the even chain. After the loop it is None for a list with five nodes, so the even chain is dropped. For 1 -> 2 -> 3 -> 4 -> 5 the result is 1 -> 3 -> 5. The fix is to save the start of the even chain in even_head before the loop and join to even_head at the end.

Summary

• A partition walks the list once and moves each node into one of two chains, saving cur.next before each move.
• A chain keeps its last node and a dummy node in front, so each add costs the same and empty chains need no special case.
• Joining sets the last node of the first chain to the head of the second chain. Empty chains work because of the dummy node.
• Odd-even reordering uses two moving names and a saved even head. It decides by position, not value.
• A slow, obvious version and a random comparison catch mistakes that hand traces miss.