Merge two sorted Java node chains by moving their links

Consume two owners

The inputs are sorted by priority, acyclic, and disjoint: no node belongs to both. That last precondition is easy to miss. If both inputs share a suffix, relinking one path can create a cycle or duplicate references. The merge consumes the input chains as independent roots; callers should use only the returned head afterward.

When priorities tie, the code takes the left node first. That preserves each input's order and makes the merge stable across the two sources. It does not sort either source; a single misplaced priority in an input invalidates the output ordering. Merge sort uses the same merge idea after it has created sorted runs.

Account for tail work

Once one input is empty, attach the remaining suffix in one link change. There is no need to copy or walk that suffix again. The dummy head simplifies the first append and adds one temporary node; a production implementation can avoid it if allocation is a concern.

This is not the same as calling addAll on two java.util.LinkedList objects. The JDK collection owns private nodes and may allocate nodes for the destination. Aliased addAll input has a separate, explicitly documented boundary.

Working program

public class MergeDispatchPriorities {
    static final class Node {
        final int priority;
        final String dispatchId;
        Node next;
        Node(int priority, String dispatchId, Node next) {
            this.priority = priority; this.dispatchId = dispatchId; this.next = next;
        }
    }
    static Node merge(Node left, Node right) {
        Node sentinel = new Node(Integer.MIN_VALUE, "sentinel", null);
        Node tail = sentinel;
        while (left != null && right != null) {
            if (left.priority <= right.priority) {
                Node selected = left; left = left.next; tail.next = selected;
            } else {
                Node selected = right; right = right.next; tail.next = selected;
            }
            tail = tail.next;
        }
        tail.next = left != null ? left : right;
        return sentinel.next;
    }
    static String labels(Node head) {
        StringBuilder result = new StringBuilder();
        for (Node current = head; current != null; current = current.next) {
            if (result.length() > 0) result.append(",");
            result.append(current.dispatchId);
        }
        return result.toString();
    }
    public static void main(String[] args) {
        Node left = new Node(11, "left-11", new Node(47, "left-47", null));
        Node right = new Node(11, "right-11", new Node(32, "right-32", null));
        System.out.println(labels(merge(left, right)));
    }
}

Output

left-11,right-11,right-32,left-47

Cost and ownership

For n and m input nodes, the merge performs O(n + m) comparisons and link visits with O(1) extra node storage. The dummy node is not part of the returned chain. Input nodes are reused, so the caller gives up independent ownership of both old roots.

Common Mistakes

• Do not merge chains that share a node or contain cycles.
• Do not assume the method repairs unsorted inputs.
• Do not keep mutating an old input root as though it still names a separate chain.

Read next

Find the entry of a cycle in a Java singly linked chain, Reverse a singly linked chain in Java without allocating new nodes, Java merge sort: stable merging and one scratch buffer, Java LinkedList addAll: snapshot an aliased source.

Continue with owned-node algorithms

Continue with Stable merge sort for a singly linked chain in Java, Stable partition of a singly linked chain in Java.