Bài toán này yêu cầu kết hợp hai danh sách liên kết đơn đã được sắp xếp tăng dần thành một danh sách liên kết mới cũng sắp xếp tăng dần. Danh sách kết quả được tạo ra bằng cách nối tất cả các nút từ hai danh sách ban đầu.

Ví dụ:

Input: ds1 = [1,2,4], ds2 = [1,3,4]
Output: [1,1,2,3,4,4]

Input: ds1 = [], ds2 = []
Output: []

Input: ds1 = [], ds2 = [0]
Output: [0]

Phương pháp giải quyết

1. Phương pháp lặp (Iterative)

Giả sử chúng ta có hai danh sách liên kết đơn đã sắp xếp là danhSach1 và danhSach2. Vì cả hai danh sách đều có thứ tự, chúng ta có thể duyệt qua chúng và chọn nút có giá trị nhỏ hơn để thêm vào danh sách kết quả. Sau khi một nút được thêm vào, con trỏ của danh sách tương ứng sẽ di chuyển tới nút kế tiếp.

Để đơn giản hóa việc xử lý các trường hợp biên của danh sách kết quả, chúng ta có thể sử dụng một nút "giả" (dummy head node hay sentinel node). Con trỏ Next của nút giả này sẽ trỏ đến nút đầu tiên của danh sách kết quả thực sự.

1. Tạo một nút giả nutGia để làm điểm khởi đầu cho danh sách kết quả. Một con trỏ hienTai sẽ được dùng để duyệt và xây dựng danh sách.
2. Duyệt đồng thời danhSach1 và danhSach2 cho đến khi một trong hai danh sách trống:
   • Nếu giá trị của nút hiện tại trong danhSach1 nhỏ hơn giá trị của nút hiện tại trong danhSach2, nối nút từ danhSach1 vào danh sách kết quả (thông qua hienTai.Next), sau đó di chuyển con trỏ danhSach1 tới nút kế tiếp.
   • Ngược lại, nối nút từ danhSach2 vào danh sách kết quả, và di chuyển con trỏ danhSach2 tới nút kế tiếp.
   • Sau mỗi lần nối, di chuyển con trỏ hienTai tới nút vừa được thêm vào.
3. Khi vòng lặp kết thúc, một trong hai danh sách (hoặc cả hai) đã trống. Nối phần còn lại của danh sách không trống vào cuối danh sách kết quả (thông qua hienTai.Next).
4. Trả về nutGia.Next làm đầu của danh sách liên kết đã hợp nhất.

Golang:

/**
 * Định nghĩa cho nút trong danh sách liên kết đơn.
 */
type Node struct {
    Val  int
    Next *Node
}

// gopHaiDanhSach hợp nhất hai danh sách liên kết đã sắp xếp.
func gopHaiDanhSach(ds1 *Node, ds2 *Node) *Node {
    // Nút giả (dummy head) để đơn giản hóa việc xử lý trường hợp danh sách rỗng
    // và làm điểm khởi đầu cho danh sách kết quả.
    nutGia := &Node{}
    conTroHienTai := nutGia // Con trỏ để duyệt và xây dựng danh sách mới

    // Duyệt qua cả hai danh sách cho đến khi một trong hai hết nút.
    for ds1 != nil && ds2 != nil {
        if ds1.Val < ds2.Val {
            // Nút của ds1 có giá trị nhỏ hơn, nối vào danh sách kết quả.
            conTroHienTai.Next = ds1
            ds1 = ds1.Next // Di chuyển con trỏ ds1 lên nút kế tiếp.
        } else {
            // Nút của ds2 có giá trị nhỏ hơn hoặc bằng, nối vào danh sách kết quả.
            conTroHienTai.Next = ds2
            ds2 = ds2.Next // Di chuyển con trỏ ds2 lên nút kế tiếp.
        }
        conTroHienTai = conTroHienTai.Next // Di chuyển con trỏ hiện tại lên nút vừa được thêm vào.
    }
    
    // Sau khi vòng lặp kết thúc, một trong hai danh sách (hoặc cả hai) đã trống.
    // Nối phần còn lại của danh sách chưa hết (nếu có) vào cuối danh sách kết quả.
    if ds1 != nil {
        conTroHienTai.Next = ds1
    } else {
        conTroHienTai.Next = ds2
    }
    
    // Trả về nút tiếp theo của nút giả, đây là đầu của danh sách hợp nhất thực sự.
    return nutGia.Next
}

C++:

/**
 * Định nghĩa cho nút trong danh sách liên kết đơn.
 */
struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

class SolutionIterative {
public:
    ListNode* hopNhatHaiDS(ListNode* danhSach1, ListNode* danhSach2) {
        // Tạo một nút bảo vệ (dummy head) để đơn giản hóa việc quản lý danh sách kết quả.
        ListNode* nutBaoVe = new ListNode(-1);
        ListNode* conTro = nutBaoVe; // Con trỏ dùng để xây dựng danh sách mới.

        // Duyệt qua cả hai danh sách chừng nào cả hai đều còn nút.
        while (danhSach1 != nullptr && danhSach2 != nullptr) {
            if (danhSach1->val < danhSach2->val) {
                // Nếu nút từ danhSach1 nhỏ hơn, nối nó vào danh sách kết quả.
                conTro->next = danhSach1;
                danhSach1 = danhSach1->next; // Di chuyển con trỏ danhSach1.
            } else {
                // Ngược lại, nối nút từ danhSach2 vào danh sách kết quả.
                conTro->next = danhSach2;
                danhSach2 = danhSach2->next; // Di chuyển con trỏ danhSach2.
            }
            conTro = conTro->next; // Di chuyển con trỏ xây dựng danh sách.
        }

        // Sau vòng lặp, một trong hai danh sách có thể còn phần tử.
        // Nối trực tiếp phần còn lại của danh sách đó vào cuối danh sách kết quả.
        if (danhSach1 != nullptr) {
            conTro->next = danhSach1;
        } else {
            conTro->next = danhSach2;
        }

        // Trả về nút đầu tiên thực sự của danh sách, bỏ qua nút bảo vệ.
        return nutBaoVe->next;
    }
};

2. Phương pháp đệ quy (Recursive)

Phương pháp đệ quy mô hình hóa quá trình hợp nhất bằng cách xem xét các trường hợp cơ bản và bước đệ quy:

• **Trường hợp cơ bản:**
  • Nếu dauDS1 (đầu danh sách 1) là nullptr, thì không có gì để hợp nhất từ danh sách 1, chỉ cần trả về dauDS2.
  • Tương tự, nếu dauDS2 (đầu danh sách 2) là nullptr, trả về dauDS1.
• **Bước đệ quy:**
  • So sánh giá trị của nút đầu tiên của dauDS1 và dauDS2.
  • Nếu dauDS1->val nhỏ hơn dauDS2->val:
    • Nút dauDS1 sẽ là đầu của danh sách hợp nhất hiện tại.
    • Phần còn lại của danh sách hợp nhất sẽ là kết quả của việc đệ quy hợp nhất dauDS1->next và dauDS2.
  • Ngược lại (nếu dauDS2->val nhỏ hơn hoặc bằng dauDS1->val):
    • Nút dauDS2 sẽ là đầu của danh sách hợp nhất hiện tại.
    • Phần còn lại của danh sách hợp nhất sẽ là kết quả của việc đệ quy hợp nhất dauDS1 và dauDS2->next.

C++:

/**
 * Định nghĩa cho nút trong danh sách liên kết đơn.
 */
struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

class SolutionRecursive {
public:
    ListNode* hopNhatDeQuy(ListNode* dauDS1, ListNode* dauDS2) {
        // Trường hợp cơ bản: nếu một trong các danh sách rỗng, trả về danh sách còn lại.
        if (dauDS1 == nullptr) {
            return dauDS2;  
        }
        if (dauDS2 == nullptr) {  
            return dauDS1;  
        }
        
        ListNode* dauKetQua; // Nút đầu của danh sách hợp nhất hiện tại
        
        // Bước đệ quy: so sánh giá trị các nút đầu và gọi đệ quy cho phần còn lại.
        if (dauDS1->val < dauDS2->val) {
            dauKetQua = dauDS1;
            // Nút tiếp theo của dauKetQua là kết quả của việc hợp nhất phần còn lại của dauDS1 và toàn bộ dauDS2.
            dauKetQua->next = hopNhatDeQuy(dauDS1->next, dauDS2);
        } else {
            dauKetQua = dauDS2;
            // Nút tiếp theo của dauKetQua là kết quả của việc hợp nhất toàn bộ dauDS1 và phần còn lại của dauDS2.
            dauKetQua->next = hopNhatDeQuy(dauDS1, dauDS2->next);
        }
        
        return dauKetQua;
    }
};