Merge Linked Lists

Merging two sorted chains

Suppose two singly linked lists are already sorted in ascending order. To obtain one sorted chain, we do not need to copy all values into an array and sort them again. We only need to compare the current first nodes of the two unprocessed parts and choose the smaller one.

One pass through two lists

Node dummy = new Node(0);
Node tail = dummy;

while (first != null && second != null) {
    if (first.value <= second.value) {
        tail.next = first;
        first = first.next;
    } else {
        tail.next = second;
        second = second.next;
    }

    tail = tail.next;
}

tail.next = first != null ? first : second;
Node merged = dummy.next;

tail always points to the last node of the result built so far. After choosing the smaller node, the corresponding first or second reference moves forward. When one list ends, the remainder of the other is already sorted and can be attached as a whole.

Why use a dummy node

The temporary dummy node removes the special case for the first appended element: from the beginning, the result has a node to which selected elements can be attached through tail.next. The real result head is stored in dummy.next.

If the first list contains n nodes and the second contains m, each original node is processed at most once. Therefore, the running time is O(n + m). The algorithm reuses the existing nodes and, apart from the helper dummy, does not create copies of the elements.