Linked list merge & reorder

O(n + m)

Build a new list by splicing nodes from two (or more) lists in order, using a dummy head node so you never special-case the first insert, then advance whichever source list has the smaller current node.

Signals

merge two sorted linked listsmerge k sorted listsreorder a list (interleave front and back halves)rearrange nodes without copying values into an arraydummy head / sentinel node

Template

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

Looks similar, isn't

Fast comparison sort (merge sort): Merge sort's merge step compares and combines two array slices by index. List merging reuses the same 'compare smallest, advance one side' idea but splices existing nodes by rewiring .next through a dummy head; there is no array to divide or index into.

n + m nodes total across lists -> O(n + m): each node is visited and spliced exactly once.

Learn this pattern