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.

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;
}

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?

These phrases in a problem statement point here:

• •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

What is Linked list merge & reorder confused with?

• 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?

• 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?

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).