Stable partition of a singly linked chain in Java

Last updated: 1 Oct 20264 min read

tutorial

A stable linked-chain partition relinks existing nodes into two groups while preserving their original order within each group.

Detach before appending

Maintain one tail for records below the threshold and another for the rest. Take a node from the input, save its original successor, then set its next to null before appending it to one group. Detachment prevents an old successor from silently linking the groups or leaving a cycle when the two tails are joined.

For this fixture, priorities below 50 go first. The records with priorities 70 and 55 keep their mutual order, as do 20 and 35. A sort would change more than the partition contract and usually need extra comparisons.

Avoid hidden input assumptions

The input must be acyclic and privately owned for mutation. A null head is valid and returns null. Reusing an input node from another chain creates aliasing between the two owners; establish a single owner or copy the nodes first. Intersection by identity can detect a shared tail before destructive operations.

This differs from the collection's stable sort: sorting orders every pair, while a partition only classifies against a threshold.

Working program

public class PartitionDispatchPriority {
    static final class Node {
        final String dispatchId;
        final int priority;
        Node next;
        Node(String dispatchId, int priority, Node next) {
            this.dispatchId = dispatchId; this.priority = priority; this.next = next;
        }
    }
    static Node partition(Node head, int threshold) {
        Node earlyRoot = new Node("early", 0, null);
        Node laterRoot = new Node("later", 0, null);
        Node earlyTail = earlyRoot, laterTail = laterRoot;
        for (Node cursor = head; cursor != null;) {
            Node following = cursor.next;
            cursor.next = null;
            if (cursor.priority < threshold) { earlyTail.next = cursor; earlyTail = cursor; }
            else { laterTail.next = cursor; laterTail = cursor; }
            cursor = following;
        }
        earlyTail.next = laterRoot.next;
        return earlyRoot.next;
    }
    static String labels(Node head) {
        StringBuilder result = new StringBuilder();
        for (Node cursor = head; cursor != null; cursor = cursor.next) {
            if (result.length() > 0) result.append(",");
            result.append(cursor.dispatchId);
        }
        return result.toString();
    }
    public static void main(String[] args) {
        Node head = new Node("review-70", 70,
            new Node("ship-20", 20, new Node("hold-55", 55, new Node("pack-35", 35, null))));
        System.out.println(labels(partition(head, 50)));
        System.out.println(partition(null, 50) == null);
    }
}

Output

ship-20,pack-35,review-70,hold-55
true

Cost and ownership

Each node moves through one cursor step, so the operation takes O(n) time and O(1) extra references plus two sentinel nodes. It does not clone payload objects. The two temporary sentinels are not part of the returned chain.

Common Mistakes

Do not append a node without clearing its stale next reference.
Do not promise global sorting from a two-group partition.
Do not mutate an aliased chain while another owner traverses it.