Khi xử lý các tập dữ liệu số đã được sắp xếp từ các nguồn khác nhau trong hệ thống Backend, yêu cầu hợp nhất chúng là rất phổ biến. Làm thế nào để giải quyết bài toán hợp nhất hai danh sách liên kết đã sắp xếp (Merge Two Sorted Lists) thành một danh sách liên kết sắp xếp hoàn chỉnh?

Question

Accepted Answer

Bài toán hợp nhất hai danh sách liên kết đã sắp xếp là một bài toán nền tảng giúp lập trình viên nắm vững cách thao tác trực tiếp trên các tham chiếu con trỏ.
Cơ chế hoạt động

Sử dụng một node giả (Dummy Node) làm điểm mốc khởi đầu cho danh sách kết quả, giúp đơn giản hóa việc xử lý trường hợp danh sách trống ban đầu.
Sử dụng một con trỏ hiện tại (current) để xây dựng danh sách mới.
Duyệt đồng thời qua cả hai danh sách list1 và list2, so sánh giá trị tại node hiện tại của mỗi danh sách.
Gắn node có giá trị nhỏ hơn vào current.next, sau đó dịch chuyển con trỏ của danh sách đó lên trước.
Khi một trong hai danh sách kết thúc, gắn phần còn lại của danh sách kia vào cuối danh sách kết quả.

Ví dụ cài đặt (Python)
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def mergeTwoLists(list1: ListNode, list2: ListNode) -> ListNode:
    dummy = ListNode(-1)
    current = dummy

while list1 and list2:
        if list1.val <= list2.val:
            current.next = list1
            list1 = list1.next
        else:
            current.next = list2
            list2 = list2.next
        current = current.next

# Gắn phần còn lại nếu có
    current.next = list1 if list1 else list2

return dummy.next
Lưu ý thực chiến
Thuật toán có độ phức tạp thời gian là O(N + M) với N và M là số lượng node của hai danh sách, và độ phức tạp không gian là O(1) vì không tạo node mới mà chỉ thay đổi các tham chiếu con trỏ sẵn có.

Làm Chủ Phỏng Vấn & Nâng Cao Trình Độ Chuyên Nghiệp

Tải Tuyển Tập 100+ Câu Hỏi Phỏng Vấn Chuyên Sâu (PDF)

Cần Mentor Phỏng Vấn Thử 1-1 & Tối Ưu CV?

Kiểm Tra CV Chuẩn ATS Miễn Phí

Câu hỏi linked lists liên quan cùng chủ đề