Merge Two Sorted Lists – Từ đệ quy đến thực tiễn

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)