Merge 2 sorted Linked Lists
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]
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;}