Merge 2 sorted Linked Lists

Easy

Problem

Merge two sorted linked lists into one sorted list by relinking their nodes (do not create new nodes). Return the head of the merged list.

Example 1

Input:  1 → 2 → 4 and 1 → 3 → 4
Output: 1 → 1 → 2 → 3 → 4 → 4

Also asked as: merge two sorted lists · merge k sorted linked lists

Test cases

Case 1

Input:    [1,2,4], [1,3,4]
Expected: [1,1,2,3,4,4]

Case 2

Input:    [], []
Expected: []

Case 3

Input:    [], [0]
Expected: [0]

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution2 approaches

1. Iterative with dummy head

Time O(n + m)Space O(1)

Splice the smaller current node onto a result list; attach the leftover tail at the end.

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

2. Recursive

Time O(n + m)Space O(n + m) call stack

Pick the smaller head, then recurse on the rest.

function mergeTwoLists(a, b) {
if (!a) return b;
if (!b) return a;
if (a.val <= b.val) { a.next = mergeTwoLists(a.next, b); return a; }
b.next = mergeTwoLists(a, b.next);
return b;
}