Bài Toán:
LeetCode 21: Merge Two Sorted Lists
Cho hai danh sách liên kết đã được sắp xếp tăng dần, hãy gộp chúng lại thành một danh sách liên kết mới được sắp xếp theo thứ tự tăng dần.
Ví dụ:
l1 = 1 -> 2 -> 4
l2 = 1 -> 3 -> 4
=> 1 -> 1 -> 2 -> 3 -> 4 -> 4
Vì cả hai danh sách đã được sắp xếp, ta chỉ cần duyệt qua các node để chọn ra node nhỏ hơn, rồi nối vào danh sách kết quả.
Ta sẽ triển khai theo 2 cách:
Cách 1: Dùng đệ quy
Ý tưởng:
So sánh l1.val và l2.val
Node nhỏ hơn sẽ được giữ lại, phần tiếp theo được gọi đệ quy
class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next def mergeTwoLists(l1, l2): if not l1: return l2 if not l2: return l1 if l1.val < l2.val: l1.next = mergeTwoLists(l1.next, l2) return l1 else: l2.next = mergeTwoLists(l1, l2.next) return l2
Phân tích:
Thời gian: O(m + n)
Bộ nhớ: O(m + n) do call stack
Đặc điểm:
Ngắn gọn, đẹp, hợp với giáo trì học thuật
Tuy nhiên có nguy cơ stack overflow khi danh sách rất dài
Cách 2: Dùng vòng lặp (không đệ quy)
Ý tưởng:
Dùng node tạm dummy làm đầu danh sách
So sánh l1.val và l2.val, node nhỏ hơn được nối vào kết quả
Sau khi một danh sách hết, nối danh sách còn lại
def mergeTwoLists(l1, l2): dummy = ListNode(-1) current = dummy while l1 and l2: if l1.val < l2.val: current.next = l1 l1 = l1.next else: current.next = l2 l2 = l2.next current = current.next current.next = l1 if l1 else l2 return dummy.next
Phân tích:
Thời gian: O(m + n)
Bộ nhớ: O(1)
Đặc điểm:
Ổn định, an toàn
Dù danh sách dài bao nhiêu vẫn xử lý được
Khuyến nghị sử dụng trong thực tế
Nếu bạn đang làm việc với những danh sách dài hoặc trên backend server thực tế, nên dùng cách không đệ quy.
Trong phòng vấn hoặc học thuật, hiểu cả hai cách để linh hoạt tuý đối bài toán.
Mở rộng
Bài toán Merge K Sorted Lists (LeetCode 23) – sử dụng heap
Merge Sort trên linked list
So sánh Merge Sorted Arrays (LeetCode 88)