Repository navigation
066 — Merge Two Sorted Lists
LeetCode 21 · Easy. You are given the heads of two sorted linked lists list1 and list2. Merge the two lists into one sorted list by splicing together the nodes of the first two lists, and return the head of the merged list.
Picture two lines of people, each line already sorted shortest to tallest, standing side by side. You want to merge them into a single sorted line without re-measuring anyone. So you just look at the front person of each line, let the shorter of the two step into the merged line first, and repeat — always comparing whoever's currently at the front of each line. Nobody needs to be re-sorted; the two lines already did that work for you. You're just interleaving two sorted streams by always taking the smaller front.
"Two sorted lists" plus "merge" is the tell. Whenever you're combining two already-sorted sequences into one sorted sequence, you never need to sort anything from scratch — you only need to walk both simultaneously and always advance whichever pointer is smaller. That "walk two structures side by side, advance the smaller" shape is Two Pointers applied to two separate lists instead of two ends of one list.
Dump every value from both lists into one array, sort it (ignoring that the inputs were already sorted), then build a brand-new list from the sorted values.
class ListNode {
var val: Int
var next: ListNode?
init(_ val: Int) { self.val = val }
}
func mergeTwoListsBruteForce(_ list1: ListNode?, _ list2: ListNode?) -> ListNode? {
var values: [Int] = []
var curr = list1
while let node = curr { values.append(node.val); curr = node.next }
curr = list2
while let node = curr { values.append(node.val); curr = node.next }
values.sort()
let dummy = ListNode(0)
var tail = dummy
for v in values {
tail.next = ListNode(v)
tail = tail.next!
}
return dummy.next
}
// smoke test: [1,2,4] and [1,3,4]
let bl1 = ListNode(1); bl1.next = ListNode(2); bl1.next?.next = ListNode(4)
let bl2 = ListNode(1); bl2.next = ListNode(3); bl2.next?.next = ListNode(4)
var bfWalk: ListNode? = mergeTwoListsBruteForce(bl1, bl2)
while let n = bfWalk { print(n.val, terminator: " "); bfWalk = n.next } // 1 1 2 3 4 4Big-O: O((n + m) log(n + m)) time — dominated by the sort, throwing away the fact the inputs were already sorted. O(n + m) extra space for the array.
Walk both lists at once with a dummy head, always attaching whichever front node holds the smaller value.
func mergeTwoLists(_ list1: ListNode?, _ list2: ListNode?) -> ListNode? {
let dummy = ListNode(0)
var tail = dummy
var l1 = list1
var l2 = list2
while let n1 = l1, let n2 = l2 {
if n1.val <= n2.val {
tail.next = n1
l1 = n1.next
} else {
tail.next = n2
l2 = n2.next
}
tail = tail.next!
}
tail.next = l1 ?? l2 // splice on whichever list still has leftover nodes
return dummy.next
}
// smoke test: [1,2,4] and [1,3,4]
let l1 = ListNode(1); l1.next = ListNode(2); l1.next?.next = ListNode(4)
let l2 = ListNode(1); l2.next = ListNode(3); l2.next?.next = ListNode(4)
var walk: ListNode? = mergeTwoLists(l1, l2)
while let n = walk { print(n.val, terminator: " "); walk = n.next } // 1 1 2 3 4 4
print(mergeTwoLists(nil, nil) == nil) // trueBig-O: O(n + m) time — one pass, splitting attention between the two lists but never revisiting a node. O(1) extra space (excluding the output list itself, which reuses the input nodes).
Sorting from scratch throws away information you already have for free: both inputs are already internally sorted, so the smallest remaining value across both lists is guaranteed to be sitting at one of the two front positions — never buried deeper. That means a full re-sort is pure waste; you only ever need to compare two candidates at a time (l1's current node and l2's current node), take the smaller, and advance just that one pointer. Doing this splices the existing nodes into a new order instead of allocating fresh ones, which is what drops both the time (O(n+m) instead of O((n+m) log(n+m))) and the space (O(1) instead of O(n+m)).
-
Linked Lists — the underlying data structure; splicing nodes by reassigning
nextis the sameO(1)-relink trick from that chapter. - Two Pointers — walking two lists simultaneously and always advancing the pointer sitting on the smaller value is Two Pointers across two separate structures rather than two ends of one.
-
Big-O Notation — for why
O(n + m)beatsO((n+m) log(n+m))once you exploit that both inputs are pre-sorted.
Merge Two Sorted Lists is two already-sorted lines merging into one — always let the shorter front-of-line person step in next, no re-measuring required.
Trace the optimal algorithm on list1 = [1, 2, 4] and list2 = [1, 3, 4]. At each step, which node does tail.next point to, and which pointer (l1 or l2) advances? Pay close attention to what happens when n1.val == n2.val — which list's node gets attached first, and does it matter for correctness?