Linked list merge & reorder

How does Linked list merge & reorder work?

Create a dummy node that leads nowhere yet. Its next will end up being the real head.

Keep a tail pointer starting at the dummy. Every node is appended there.

Compare the front node of each list. Append the smaller one and step that list forward.

Move the tail to the node just appended. Repeat until one of the lists runs out.

Append whatever remains of the other list. It is already sorted, so no comparison is needed.

Return dummy.next at the end. No node was copied, only re-linked.

Sources: Wikipedia: Merge algorithm

1. dummy, a = 1, b = 2Merging [1, 4] with [2, 3]. The dummy holds nothing.
2. tail = 1, a = 4, b = 21 is smaller than 2, so it is appended first.
3. tail = 2, b = 3Now 4 against 2. The 2 goes next.
4. tail = 3, b = null3 beats 4 as well. The second list is now empty.
5. 1, 2, 3, 4The rest of the first list is appended in one step.

function mergeTwoLists(a, b) {
    const dummy = { next: null };
    let tail = dummy;
    while (a && b) {
        if (a.val <= b.val) { tail.next = a; a = a.next; }
        else { tail.next = b; b = b.next; }
        tail = tail.next;
    }
    tail.next = a || b;
    return dummy.next;
}

interface ListNode {
    val: number;
    next: ListNode | null;
}

function mergeTwoLists(a: ListNode | null, b: ListNode | null): ListNode | null {
    const dummy: ListNode = { val: 0, next: null };
    let tail = dummy;
    while (a && b) {
        if (a.val <= b.val) { tail.next = a; a = a.next; }
        else { tail.next = b; b = b.next; }
        tail = tail.next;
    }
    tail.next = a ?? b;
    return dummy.next;
}

def merge_two_lists(a, b):
    dummy = Node(0)
    tail = dummy
    while a and b:
        if a.val <= b.val:
            tail.next, a = a, a.next
        else:
            tail.next, b = b, b.next
        tail = tail.next
    tail.next = a or b
    return dummy.next

function mergeTwoLists(?Node $a, ?Node $b): ?Node {
    $dummy = new Node(0);
    $tail = $dummy;
    while ($a !== null && $b !== null) {
        if ($a->val <= $b->val) { $tail->next = $a; $a = $a->next; }
        else { $tail->next = $b; $b = $b->next; }
        $tail = $tail->next;
    }
    $tail->next = $a ?? $b;
    return $dummy->next;
}

    public static ListNode mergeTwoLists(ListNode a, ListNode b) {
        ListNode dummy = new ListNode();
        ListNode tail = dummy;
        while (a != null && b != null) {
            if (a.val <= b.val) { tail.next = a; a = a.next; }
            else { tail.next = b; b = b.next; }
            tail = tail.next;
        }
        tail.next = a != null ? a : b;
        return dummy.next;
    }

    public static class ListNode {
        public int val;
        public ListNode next;
    }

    public static ListNode MergeTwoLists(ListNode a, ListNode b) {
        var dummy = new ListNode();
        var tail = dummy;
        while (a != null && b != null) {
            if (a.val <= b.val) { tail.next = a; a = a.next; }
            else { tail.next = b; b = b.next; }
            tail = tail.next;
        }
        tail.next = a ?? b;
        return dummy.next;
    }

    public class ListNode {
        public int val;
        public ListNode next;
    }

A worked example of Linked list merge & reorder

Reorder a list from both ends

Reorder a list as first, last, second, second last, and onward.

The nodes have to be relinked. Copying the values into an array is not allowed.

Find the middle with a slow and a fast pointer, then cut the list there.

Reverse the back half. Weave the two halves together one node at a time.

function reorderList(head) {
    if (!head || !head.next) return head;

    let slow = head;
    let fast = head;
    while (fast.next && fast.next.next) {
        slow = slow.next;
        fast = fast.next.next;
    }

    let second = slow.next;
    slow.next = null; // cut the list in two, or the weave loops forever

    let prev = null;
    while (second) {
        const next = second.next;
        second.next = prev;
        prev = second;
        second = next;
    }

    let first = head;
    while (prev) {
        const a = first.next;
        const b = prev.next;
        first.next = prev;
        prev.next = a;
        first = a;
        prev = b;
    }

    return head;
}

When should you use Linked list merge & reorder?

Use Linked list merge & reorder when the problem statement says “merge two sorted linked lists”, “merge k sorted lists” or “reorder a list (interleave front and back halves)”. A solution built on it usually runs in O(n + m).

• •merge two sorted linked lists
• •merge k sorted lists
• •reorder a list (interleave front and back halves)
• •rearrange nodes without copying values into an array
• •dummy head / sentinel node

The signal words of every pattern sit in one table, the algorithm patterns cheat sheet.

What is Linked list merge & reorder confused with?

Linked list merge & reorder is most often confused with Linked list reversal, Binary heap / priority queue, Fast sort (merge / quick) and Fast & slow pointers.

• Linked list reversal: Reversal flips the links inside one list. Merging re-links nodes across two lists.
• Binary heap / priority queue: With k lists a heap picks the smallest front in log k. With two lists one comparison is enough.
• Fast sort (merge / quick): The merge step of merge sort is this exact loop. Here the lists arrive already sorted.
• Fast & slow pointers: Reordering starts by finding the middle, which is that pattern. The weave afterwards is this one.

Common mistakes with Linked list merge & reorder

• Working without a dummy node

  The first append then needs a special case for the empty result. A dummy deletes that branch.

• Dropping the leftover tail

  When one list empties, the other still holds nodes. Link the whole rest in one step.

• Building new nodes

  These problems expect the original nodes relinked. Copying doubles the memory for nothing.

• Leaving a cycle behind

  Cutting a list means setting some next to null. Skipping that makes the list loop.

Which interview problems use Linked list merge & reorder?

Interview problems solved with Linked list merge & reorder include Merge two sorted lists, Merge k sorted lists, Sort list, Reorder list, Add two numbers, Partition list and Intersection of two linked lists.

• Merge two sorted lists: The plain form: a dummy and one comparison per node.
• Merge k sorted lists: A heap holds the front node of every list.
• Sort list: Split at the middle, sort both halves, then merge.
• Reorder list: Split, reverse the back half, then weave the two.
• Add two numbers: Walk both lists together and carry the overflow.
• Partition list: Two dummies, one for small values and one for the rest.
• Intersection of two linked lists: Two walkers that swap lists at the end.

What is the time and space complexity of Linked list merge & reorder?

The target complexity of Linked list merge & reorder is O(n + m).

n plus m nodes gives O(n + m) time and O(1) space. Merging k lists with a heap costs O(N log k).