Partition and odd-even reordering

Why this matters

Many list tasks begin by sorting the nodes into two groups. A quicksort step splits numbers into a small group and a large group. An order system might separate paid orders from unpaid ones. A game might send even-numbered turns to one queue and odd-numbered turns to another. In each case you walk the list once, look at each node, and send it to one of two places.

The hard part is keeping the order. Suppose the list holds 4, 9, 2, 7 and you split by "is the value even". The even group must read 4 then 2, not 2 then 4. The nodes that go to the same group must keep the order they had in the original list. Interviewers check this, because a result with the wrong order looks right at a glance and is still wrong.

This lesson builds one function that splits a list into two chains. A chain here means a linked list that is one part of a bigger list. The same function then handles three jobs: splitting by value, splitting at a position, and the odd-even reordering problem, where the nodes at odd positions come first and the nodes at even positions follow.

The lesson uses the unique_ptr type from the standard library. A unique_ptr is a pointer that owns the object it points to. When the owner goes away, the object is freed. A unique_ptr cannot be copied, only moved. Moving hands the object to a new owner and leaves the old pointer empty. An empty pointer is called null here. Reading the lesson requires only that you know what a pointer is and how a list node links to the next node.

The idea: deal each node into one of two piles

Picture a card dealer with two piles on the table. The dealer takes the top card from the deck. If the card matches the rule, it goes on pile A. If not, it goes on pile B. Each new card goes on the bottom of its pile. The cards in each pile are then in the same order they were in the deck, because later cards always sit below earlier cards.

A list works the same way. Walk the list from the head. Take the first node off the list. Decide which pile it goes to. Add it to the end of that pile. Repeat until the original list is empty. Each pile is a chain, and the order is kept because every node is added at the end.

Here is the rule "less than 5" applied to the list 1, 7, 3, 9, 5, 2.

The small pile ends up as 1, 3, 2. The rest pile ends up as 7, 9, 5. Both piles keep their original order. Joining the two piles, small first, gives 1, 3, 2, 7, 9, 5. The rest of the lesson turns this table into code.

Building the nodes

First we need a node type and a way to build test lists. Each node holds a value and a unique_ptr to the next node. The list owns every node after its head, so when the head is deleted, the whole chain is deleted with it.

#include <iostream>
#include <memory>
#include <utility>
#include <vector>
 
struct Node {
    int value;
    std::unique_ptr<Node> next;
    explicit Node(int v) : value(v) {}
};
 
using NodePtr = std::unique_ptr<Node>;
 
NodePtr from_values(const std::vector<int>& values) {
    NodePtr head;
    for (auto it = values.rbegin(); it != values.rend(); ++it) {
        auto node = std::make_unique<Node>(*it);
        node->next = std::move(head);
        head = std::move(node);
    }
    return head;
}
 
void print_list(const char* label, const Node* head) {
    std::cout << label << ":";
    for (const Node* p = head; p != nullptr; p = p->next.get()) {
        std::cout << ' ' << p->value;
    }
    std::cout << '\n';
}

from_values builds the list from the back, so each new node points at the list built so far. print_list takes a const Node*, which is a plain pointer that only reads. It uses p->next.get() to turn the owning unique_ptr into a plain pointer for the walk. The get call does not change ownership.

Two piles with dummy heads

Joining the piles at the end is easier if each pile begins with a node that holds no real value. This is a dummy node. It is a placeholder at the front of the pile. The first real node is added after the dummy, the same way as every other node, so the code does not need a special case for an empty pile. At the end, the real chain is the dummy's next, and the dummy is thrown away.

Each pile also needs a tail pointer. A tail pointer is a plain Node* that points at the last node of the pile. Adding a node means setting the tail's next and moving the tail forward. The tail pointer does not own anything. Ownership stays with the chain, so the tail can never free a node by mistake.

The split function

Here is the function that deals each node into one of two piles. It takes a predicate, which is a function that answers yes or no for one node. A predicate can be any callable thing, such as a lambda, which is a small unnamed function written inside the code.

struct Chains {
    NodePtr yes;
    NodePtr no;
};
 
template <typename Pred>
Chains split_by(NodePtr head, Pred pred) {
    NodePtr yes_dummy = std::make_unique<Node>(0);
    NodePtr no_dummy = std::make_unique<Node>(0);
    Node* yes_tail = yes_dummy.get();
    Node* no_tail = no_dummy.get();
 
    while (head) {
        NodePtr node = std::move(head);
        head = std::move(node->next);
        if (pred(*node)) {
            yes_tail->next = std::move(node);
            yes_tail = yes_tail->next.get();
        } else {
            no_tail->next = std::move(node);
            no_tail = no_tail->next.get();
        }
    }
    return Chains{std::move(yes_dummy->next), std::move(no_dummy->next)};
}

Read the loop one line at a time.

The line NodePtr node = std::move(head); takes the first node off the original list. After this line, head is null and node owns the first node.

The line head = std::move(node->next); moves the rest of the list into head. Now node->next is null, so the first node no longer links to the rest. This cut is what lets the node join a new chain without dragging the rest of the old list with it.

The if decides the pile. The predicate receives *node, which is the node itself, so it can read value or any other field.

Inside each branch, yes_tail->next = std::move(node); attaches the node to the end of its pile. Then yes_tail = yes_tail->next.get(); moves the tail pointer onto the node that was just added. The node is now the last node of its pile, and its own next is null, because the cut earlier made it null.

When the loop ends, the original list is empty and both piles are complete. The function returns both chains. The dummy nodes are destroyed when the function ends. Their next pointers were moved out, so the destruction frees only the dummy itself.

The loop is the only place where nodes move. Nothing is copied and no node is created, so the work is one pass over the list, which takes time proportional to the number of nodes.

Joining two chains

Splitting is only half the job. Often you need to put the two chains back together. The join function appends one chain after another.

NodePtr join(NodePtr first, NodePtr second) {
    if (!first) {
        return second;
    }
    Node* tail = first.get();
    while (tail->next) {
        tail = tail->next.get();
    }
    tail->next = std::move(second);
    return first;
}

If the first chain is empty, the answer is the second chain. Otherwise the function walks from the head of the first chain to its last node, and attaches the second chain there. The walk costs time proportional to the length of the first chain. Exercise 4 below shows how to avoid that walk.

Example 1: split by value

Now the first worked example. Keep the values less than 5 in one chain and send the rest to the other chain.

The rule is a lambda that captures limit by value, so the lambda has its own copy of the number 5.

NodePtr list = from_values({1, 7, 3, 9, 5, 2});
int limit = 5;
Chains parts = split_by(std::move(list), [limit](const Node& n) { return n.value < limit; });
print_list("small", parts.yes.get());
print_list("rest ", parts.no.get());
NodePtr all = join(std::move(parts.yes), std::move(parts.no));
print_list("joined", all.get());

Expected output:

small: 1 3 2
rest : 7 9 5
joined: 1 3 2 7 9 5

The small chain has 1, 3, 2 in the same order as the input. The rest chain has 7, 9, 5 in the same order. Joining them puts the small chain first.

Example 2: split at a position

Now a second example with a different rule. Instead of looking at values, look at how far each node is from the head. The first k nodes go to one chain and the rest go to the other. This is a split by index, which means a split by position.

The trick is a counter. The rule is a lambda that compares the counter with k and then adds one to the counter. The counter is position, and the lambda captures it by reference so the change is kept between calls.

Chains split_at(NodePtr head, std::size_t k) {
    std::size_t position = 0;
    return split_by(std::move(head), [&position, k](const Node&) {
        return position++ < k;
    });
}

This works only because split_by calls the rule exactly once per node and in list order. The first call is for the first node, the second call for the second node, and so on. If the function visited the nodes in a different order, the counter would no longer match the positions.

The position++ form returns the old value and then adds one. So the first call compares 0 with k, the second compares 1 with k, and so on. When k is 3, the first three nodes are yes and the rest are no.

Chains parts = split_at(from_values({10, 20, 30, 40, 50}), 3);
print_list("front", parts.yes.get());
print_list("back ", parts.no.get());

Expected output:

front: 10 20 30
back : 40 50

Splitting at a position is the first step of many list tasks. For example, to split a list in half, count the nodes first, then split at half the count. Exercise 5 does this.

Example 3: odd-even reordering

The last example is harder. The task is to move the nodes at odd positions to the front, followed by the nodes at even positions, keeping the order inside each group. Positions are counted from 1 here. So the first node, the third node and the fifth node are the odd positions. The second, fourth and sixth nodes are the even positions.

For the list 1, 2, 3, 4, 5, 6, 7 the answer is 1, 3, 5, 7, followed by 2, 4, 6.

The rule is almost the same as in the split by position. The counter starts at 0. The rule returns true when the counter is even, so the first node, the third node and the fifth node go to the yes chain. That is exactly the set of nodes at odd positions when counting from 1.

NodePtr odd_even(NodePtr head) {
    std::size_t position = 0;
    Chains parts = split_by(std::move(head), [&position](const Node&) {
        return position++ % 2 == 0;
    });
    return join(std::move(parts.yes), std::move(parts.no));
}

The function splits the list into two chains and then joins them, odd positions first. It uses no new nodes. Each node is moved once, so the time is proportional to the length of the list.

print_list("odd-even 7", odd_even(from_values({1, 2, 3, 4, 5, 6, 7})).get());
print_list("odd-even 6", odd_even(from_values({1, 2, 3, 4, 5, 6})).get());
print_list("odd-even 1", odd_even(from_values({9})).get());
print_list("odd-even 0", odd_even(from_values({})).get());

Expected output:

odd-even 7: 1 3 5 7 2 4 6
odd-even 6: 1 3 5 2 4 6
odd-even 1: 9
odd-even 0:

The empty list gives an empty result. A list with one node is unchanged. Both cases work without any special code, because the dummy nodes and the empty-chain check in join take care of them.

Example 4: duplicate values

Equal values are a common trap. The split keeps every node, including repeats, and keeps their order. Here the rule is "less than 4" and the list contains several 4s.

Chains parts = split_by(from_values({4, 4, 1, 4, 2}), [](const Node& n) { return n.value < 4; });
print_list("dup small", parts.yes.get());
print_list("dup rest ", parts.no.get());

Expected output:

dup small: 1 2
dup rest : 4 4 4

Each 4 is in the rest chain, in the same order. Nothing is merged or dropped. A split never removes a node. If your output is shorter than the input, the bug is in a join or in a branch that forgot to move a node.

Putting the examples together

The four examples use the same three functions. The full program is the Node code, the split_by function, the join function, the split_at and odd_even functions, and a main function that runs each example. The main function looks like this.

int main() {
    {
        NodePtr list = from_values({1, 7, 3, 9, 5, 2});
        int limit = 5;
        Chains parts = split_by(std::move(list), [limit](const Node& n) { return n.value < limit; });
        print_list("small", parts.yes.get());
        print_list("rest ", parts.no.get());
        NodePtr all = join(std::move(parts.yes), std::move(parts.no));
        print_list("joined", all.get());
    }
    {
        Chains parts = split_at(from_values({10, 20, 30, 40, 50}), 3);
        print_list("front", parts.yes.get());
        print_list("back ", parts.no.get());
    }
    {
        print_list("odd-even 7", odd_even(from_values({1, 2, 3, 4, 5, 6, 7})).get());
        print_list("odd-even 6", odd_even(from_values({1, 2, 3, 4, 5, 6})).get());
        print_list("odd-even 1", odd_even(from_values({9})).get());
        print_list("odd-even 0", odd_even(from_values({})).get());
    }
    {
        Chains parts = split_by(from_values({4, 4, 1, 4, 2}), [](const Node& n) { return n.value < 4; });
        print_list("dup small", parts.yes.get());
        print_list("dup rest ", parts.no.get());
    }
    return 0;
}

Expected output of the whole program:

small: 1 3 2
rest : 7 9 5
joined: 1 3 2 7 9 5
front: 10 20 30
back : 40 50
odd-even 7: 1 3 5 7 2 4 6
odd-even 6: 1 3 5 2 4 6
odd-even 1: 9
odd-even 0:
dup small: 1 2
dup rest : 4 4 4

To run it, put the Node code, split_by, join, split_at and odd_even above main in one file. Then compile with g++ -std=c++20 -Wall -Wextra and run the program.

Common mistakes

Copying a unique_ptr instead of moving it

A beginner often writes the first line of the loop as a copy. The compiler stops the program with an error like this.

#include <memory>
 
struct Node {
    int value;
    std::unique_ptr<Node> next;
    explicit Node(int v) : value(v) {}
};
 
using NodePtr = std::unique_ptr<Node>;
 
int main() {
    NodePtr head = std::make_unique<Node>(1);
    NodePtr node = head;
    return node->value;
}

The compiler reports the error on line 13, the line with NodePtr node = head;.

error: use of deleted function 'std::unique_ptr<_Tp, _Dp>::unique_ptr(const std::unique_ptr<_Tp, _Dp>&) [with _Tp = Node; _Dp = std::default_delete<Node>]'
   13 |     NodePtr node = head;

The message is long, but the important part is "use of deleted function" and the word unique_ptr. A unique_ptr has no copy operation. The fix is to move the pointer with std::move, as in NodePtr node = std::move(head);. After the move, head is null, which is correct, because the node now belongs to node.

Forgetting to cut the link to the rest of the list

This mistake does not stop the compiler. It gives a wrong answer with no error. The bug is a missing line in the loop. The line head = std::move(node->next); is gone.

while (head) {
    NodePtr node = std::move(head);
    if (node->value < 5) {
        yes_tail->next = std::move(node);
        yes_tail = yes_tail->next.get();
    } else {
        no_tail->next = std::move(node);
        no_tail = no_tail->next.get();
    }
}

Run this on the list 1, 7, 3, 9, 5, 2 and the output is wrong.

small: 1 7 3 9 5 2
rest :

The first node, with value 1, is moved into the small chain. It still holds the pointer to the rest of the list, because nothing cut that link. So the whole list rides along in the small chain. The loop then finds head empty and stops. No crash, no warning. Always cut the link before you attach the node to a new chain.

Keeping a raw pointer to a node that has been freed

A tail pointer points at a node that some other object owns. If the owner is destroyed first, the tail points at memory that is no longer valid. The next read or write through that pointer is a use after free bug. The code below shows the mistake in its simplest form.

#include <iostream>
#include <memory>
 
struct Node {
    int value;
    std::unique_ptr<Node> next;
    explicit Node(int v) : value(v) {}
};
 
int main() {
    Node* tail = nullptr;
    {
        auto node = std::make_unique<Node>(5);
        tail = node.get();
    }
    std::cout << tail->value << '\n';
    return 0;
}

The variable node owns the object and is destroyed at the closing brace. The pointer tail still holds the old address. Building with the address sanitizer, which is a checking mode of the compiler (-fsanitize=address), gives this report.

=================================================================
==173755==ERROR: AddressSanitizer: heap-use-after-free on address 0x745653fe0010 at pc 0x627c15c3a432 bp 0x7fffe21ff710 sp 0x7fffe21ff700
READ of size 4 at 0x745653fe0010 thread T0
    #0 0x627c15c3a431 in main mistake_dangling.cpp:16

The report continues with more lines. The path in front of the file name is shortened here. The addresses change on each run, but the words "heap-use-after-free" and the line number stay the same. Without the sanitizer, the same program may print a wrong number or appear to work, which makes this bug hard to find. The fix is to link the node into the chain first, with tail->next = std::move(node);, and only then take the raw pointer from the chain. A raw pointer must never outlive the owner it points into.

Practice

Exercise 1. Apply the split by value rule "less than 3" to the list 5, 1, 3, 2. Write the small chain and the rest chain.

Show the answer

The small chain is 1, 2. The rest chain is 5, 3. Both keep their original order. The node with value 3 is not less than 3, so it goes to the rest chain.

Exercise 2. Predict the output of odd_even for the lists 1, 2, 3, 4 and 1, 2, 3, 4, 5 and 8, 9.

Show the answer

For 1, 2, 3, 4 the output is 1 3 2 4. For 1, 2, 3, 4, 5 the output is 1 3 5 2 4. For 8, 9 the output is 8 9. Running these three lists through the functions in this lesson gives exactly these lines.

Exercise 3. Write a call that splits a list into its even values and its odd values, keeping order. Use split_by. Give the even chain as the yes chain.

Show the answer

Chains parts = split_by(from_values({4, 7, 2, 9, 6}), [](const Node& n) { return n.value % 2 == 0; });
print_list("evens", parts.yes.get());
print_list("odds ", parts.no.get());

The output is evens: 4 2 6 and odds : 7 9. The % operator gives the remainder after division by 2. A remainder of 0 means the value is even.

Exercise 4. The join function walks the first chain to find its last node. Explain when this walk costs the most, and describe how to avoid it.

Show the answer

The walk costs the most when the first chain is long, because the function visits every node in it. The split function already knows the tail of each chain. If split_by returned the tail pointers along with the chains, a join could attach the second chain at once. The cost would then be the same no matter how long the first chain is. The trade-off is one more value to return and keep correct.

Exercise 5. Write a function that splits a list into two halves. When the number of nodes is odd, the first half should get the extra node. For the list 1, 2, 3, 4, 5, the first half is 1, 2, 3 and the second half is 4, 5.

Show the answer

Count the nodes first, then split at (n + 1) / 2. The integer division rounds down, so adding 1 before dividing makes the first half one node longer when n is odd. For five nodes, (5 + 1) / 2 is 3.

std::size_t count = 0;
for (const Node* p = list.get(); p != nullptr; p = p->next.get()) {
    ++count;
}
Chains halves = split_at(std::move(list), (count + 1) / 2);

Printing the two halves with print_list, as in Example 2, shows front: 1 2 3 and back : 4 5 for the input 1, 2, 3, 4, 5.

Summary

• Split a list by walking it once and moving each node onto the end of one of two chains, so the order inside each chain is kept.
• Use dummy head nodes and tail pointers so the first node of each chain is added the same way as every other node.
• Cut the link to the rest of the list before attaching a node to a new chain, or the rest of the list comes along with it.
• Split by position with a counter that the rule increments once per node, and rely on the split visiting nodes in order.
• Odd-even reordering is a split by position, where the even counter values go to the first chain, followed by a join.