Gộp Hai Danh Sách Đã Sắp XếpMerge Two Sorted Lists
Hiểu bài
Cho head của hai danh sách liên kết (linked list) đều đã sắp xếp tăng dần.
Gộp chúng thành một danh sách sắp xếp duy nhất bằng cách nối lại các node có sẵn, trả về head mới.
// l1: 1 → 2 → 4
// l2: 1 → 3 → 4
// kết quả: 1 → 1 → 2 → 3 → 4 → 4Vì hai danh sách đã sắp xếp, ta chỉ cần so đầu hai danh sách và lần lượt lấy node nhỏ hơn — y hệt bước "merge" trong merge sort.
Một node giả (dummy) ở đầu giúp tránh xử lý riêng phần tử đầu tiên.
Xem cách cơ bản (chậm hơn)
O((n+m) log(n+m)) time, O(n+m) spacefunction mergeNaive(l1: ListNode | null, l2: ListNode | null): ListNode | null {
const vals: number[] = []
for (let n = l1; n; n = n.next) vals.push(n.val)
for (let n = l2; n; n = n.next) vals.push(n.val)
vals.sort((a, b) => a - b) // sắp xếp lại dù 2 danh sách đã sắp xếp sẵn
const dummy = new ListNode(0)
let tail = dummy
for (const v of vals) { tail.next = new ListNode(v); tail = tail.next }
return dummy.next
}Cách này gom hết giá trị rồi sort lại — phí công vì hai danh sách vốn đã sắp xếp.
Tận dụng điều đó bằng hai con trỏ thì chỉ mất O(n+m).
Lời giải tối ưu
O(n + m) time, O(1) spacefunction mergeTwoLists(l1: ListNode | null, l2: ListNode | null): ListNode | null {
const dummy = new ListNode(0) // node giả để gắn kết quả
let tail = dummy
while (l1 && l2) {
if (l1.val <= l2.val) {
tail.next = l1
l1 = l1.next
} else {
tail.next = l2
l2 = l2.next
}
tail = tail.next
}
tail.next = l1 ?? l2 // nối phần còn lại (một trong hai đã hết)
return dummy.next
}Cách tối ưu dùng hai con trỏ chạy đầu hai danh sách; mỗi bước nối node nhỏ hơn vào đuôi kết quả rồi tiến con trỏ đó.
- Dùng
<=để giữ thứ tự ổn định khi bằng nhau. - Khi một danh sách hết, nối thẳng phần còn lại vì nó đã sắp xếp.
- Không tạo node mới nên bộ nhớ phụ O(1).
Chạy thử từng bước
- 1
l1=1, l2=1. 1<=1 → nối l1(1) vào đuôi; l1=2; tail=node(1).
picked:"l1=1"l1:2l2:1out:"1" - 2
l1=2, l2=1. 2>1 → nối l2(1); l2=3; tail tiến. out: 1→1.
picked:"l2=1"l1:2l2:3out:"1→1" - 3
l1=2, l2=3. 2<=3 → nối l1(2); l1=4. out: 1→1→2.
picked:"l1=2"l1:4l2:3out:"1→1→2" - 4
l1=4, l2=3. 4>3 → nối l2(3); l2=4. out: 1→1→2→3.
picked:"l2=3"l1:4l2:4out:"1→1→2→3" - 5
l1=4, l2=4. 4<=4 → nối l1(4); l1=null → dừng.
Nối phần còn lại l2(4). out: 1→1→2→3→4→4.
out:"1→1→2→3→4→4"
Trường hợp biên phải nhớ
Cả hai danh sách rỗng → dummy.next = null → trả về null.
Một danh sách rỗng → vòng lặp không chạy, nối thẳng danh sách còn lại.
Mọi phần tử l1 nhỏ hơn l2 → l1 cạn trước, phần đuôi là toàn bộ l2.
Giá trị trùng nhau giữa hai danh sách → dùng <= để giữ thứ tự ổn định.