21. Merge Two Sorted Lists

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

Example 1:

Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]

Example 2:

Input: list1 = [], list2 = []
Output: []

Example 3:

Input: list1 = [], list2 = [0]
Output: [0]

Constraints:

The number of nodes in both lists is in the range [0, 50].
-100 <= Node.val <= 100
Both list1 and list2 are sorted in non-decreasing order.

/**

* Definition for singly-linked list.

* 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 Solution {

public:

ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {

// 1. Tạo một nút giả để làm điểm tựa

ListNode dummy(0);

ListNode* tail = &dummy;

// 2. Duyệt khi cả hai danh sách đều còn phần tử

while (list1 != nullptr && list2 != nullptr) {

if (list1->val <= list2->val) {

tail->next = list1; // Nối nút từ list1 vào

list1 = list1->next; // Di chuyển list1 tới nút tiếp theo

} else {

tail->next = list2; // Nối nút từ list2 vào

list2 = list2->next; // Di chuyển list2 tới nút tiếp theo

}

tail = tail->next; // Di chuyển con trỏ tail của danh sách kết quả

}

// 3. Nếu một danh sách vẫn còn phần tử, nối nốt phần còn lại đó vào

if (list1 != nullptr) {

tail->next = list1;

} else {

tail->next = list2;

}

// 4. Trả về head thực sự (nằm sau nút dummy)

return dummy.next;

}

};

// dùng đệ quy

// if (!list1) return list2;

// if (!list2) return list1;

// if (list1->val < list2->val) {

// list1->next = mergeTwoLists(list1->next, list2);

// return list1;

// } else {

// list2->next = mergeTwoLists(list1, list2->next);

// return list2;

// }

Thực hiện dry run (chạy từng bước bằng tay) với ví dụ:

list1: 1 → 2 → 4
list2: 1 → 3 → 4

Khởi tạo ban đầu

Dummy Node: Tạo một nút giả dummy (giá trị 0).
Tail Pointer: Con trỏ tail ban đầu trỏ vào dummy.
Trạng thái: dummy -> (trống), tail ở dummy.

Các bước thực hiện (Vòng lặp While)

Bước	So sánh giá trị	Hành động	Danh sách kết quả (sau dummy)	Trạng thái tiếp theo
1	`list1(1)` vs `list2(1)`	1 <= 1 (Đúng). Chọn `list1`.	`1`	`list1` tiến tới `2`, `tail` tiến tới `1`
2	`list1(2)` vs `list2(1)`	2 <= 1 (Sai). Chọn `list2`.	`1 -> 1`	`list2` tiến tới `3`, `tail` tiến tới `1` (thứ hai)
3	`list1(2)` vs `list2(3)`	2 <= 3 (Đúng). Chọn `list1`.	`1 -> 1 -> 2`	`list1` tiến tới `4`, `tail` tiến tới `2`
4	`list1(4)` vs `list2(3)`	4 <= 3 (Sai). Chọn `list2`.	`1 -> 1 -> 2 -> 3`	`list2` tiến tới `4`, `tail` tiến tới `3`
5	`list1(4)` vs `list2(4)`	4 <= 4 (Đúng). Chọn `list1`.	`1 -> 1 -> 2 -> 3 -> 4`	`list1` tiến tới `nullptr` (hết), `tail` tiến tới `4`

Bước cuối cùng (Sau vòng lặp)

Lúc này, vòng lặp dừng lại vì list1 == nullptr.

Kiểm tra điều kiện còn dư: Thuật toán kiểm tra thấy list2 vẫn còn một nút (giá trị 4).
Kết nối nhanh: Thay vì duyệt tiếp, thuật toán chỉ cần thực hiện một phép gán duy nhất: tail->next = list2.
Kết quả: Danh sách trở thành 1 -> 1 -> 2 -> 3 -> 4 -> 4.

Trả về kết quả

Hàm trả về dummy.next, tức là bắt đầu từ nút 1 đầu tiên, bỏ qua nút dummy (0) mà ta đã tạo ra lúc đầu.

Tại sao con trỏ `tail` lại quan trọng?

Hãy tưởng tượng tail giống như "người thợ xây". Mỗi khi chúng ta chọn được một viên gạch (nút) nhỏ hơn từ list1 hoặc list2, tail sẽ đặt viên gạch đó xuống và bước lên trên viên gạch đó để sẵn sàng nhận viên tiếp theo. Nếu không có tail, chúng ta sẽ mất dấu vị trí cuối cùng của danh sách đang xây dựng.

1. `tail = tail->next;`

Hãy tưởng tượng đang đi xâu một chuỗi hạt.

tail giống như cái ngón tay, luôn giữ ở hạt cuối cùng vừa mới xâu xong.
tail->next = list1; là bước lấy một hạt mới (list1) xâu vào sợi dây ngay sau hạt hiện tại.
tail = tail->next; chính là bước nhấc ngón tay lên và đặt nó vào hạt mới vừa xâu đó.

Mục đích: Để ở vòng lặp kế tiếp, khi bạn tìm được hạt tiếp theo, bạn biết chính xác chỗ nào để "móc" nó vào. Nếu không có dòng này, tail sẽ đứng yên mãi ở nút dummy, và mọi hạt bạn xâu vào đều sẽ đè lên nhau ở cùng một vị trí.

2. Tại sao `while` dùng `&&` mà vẫn cần bước "Nối nốt phần còn lại"?

Đây là một chi tiết rất tinh tế về logic:

Tại sao dùng `&&` (AND)?

Vòng lặp while (list1 != nullptr && list2 != nullptr) có nghĩa là: "Chỉ tiếp tục so sánh khi cả hai danh sách đều còn phần tử." Chỉ cần một trong hai danh sách hết sạch (bằng nullptr), vòng lặp sẽ dừng ngay lập tức. Tại sao? Vì nếu một danh sách đã hết, bạn đâu còn gì nữa mà "so sánh" (đâu thể so sánh số 5 với một khoảng trống vô hình).

Tại sao cần bước "Nối nốt phần còn lại"?

Khi vòng lặp dừng lại, thường sẽ rơi vào tình trạng: một danh sách đã hết sạch, nhưng danh sách kia vẫn còn một hoặc nhiều phần tử.

Ví dụ:

list1: [1, 2]
list2: [1, 3, 4, 5, 6]

Vòng lặp sẽ chạy để so sánh và nối các số 1, 1, 2.
Lúc này list1 trở thành nullptr. Vòng lặp dừng.
list2 vẫn còn đoạn [3, 4, 5, 6].

Vì list2 vốn dĩ đã được sắp xếp sẵn, chúng ta không cần dùng vòng lặp để nối từng nút nữa. Chỉ cần một nhát cắt-dán duy nhất: tail->next = list2; Dòng này sẽ gắn toàn bộ đoạn còn lại của list2 vào đuôi của danh sách kết quả. Điều này cực kỳ hiệu quả về hiệu suất!

Tóm tắt bằng hình ảnh ẩn dụ:

Vòng lặp while với &&: Là cuộc đua song mã. Khi một vận động viên về đích trước, cuộc đua so tài kết thúc.
Bước nối phần dư: Là lúc bạn bê nguyên đoạn đường còn lại của vận động viên chưa về đích gắn vào kết quả vì họ không còn đối thủ để so tài nữa.

Quy trình Dry Run (Từng bước đệ quy) với `list1 = [1, 2, 4]` và `list2 = [1, 3, 4]`.

Mỗi lần hàm mergeTwoLists được gọi, chúng ta so sánh hai giá trị đầu tiên và "tạm giữ" nút nhỏ hơn lại để chờ kết quả từ các bước sau.

Bước 1: Gọi hàm lần 1

list1 (1), list2 (1). Vì 1 <= 1, ta chọn list1.
Giữ lại: Nút 1 (của list1).
Việc cần làm: Chờ kết quả của merge(list1->next, list2) tức là merge([2, 4], [1, 3, 4]).

Bước 2: Gọi hàm lần 2

So sánh 2 và 1. Chọn list2.
Giữ lại: Nút 1 (của list2).
Việc cần làm: Chờ kết quả của merge([2, 4], [3, 4]).

Bước 3: Gọi hàm lần 3

So sánh 2 và 3. Chọn list1.
Giữ lại: Nút 2.
Việc cần làm: Chờ kết quả của merge([4], [3, 4]).

Bước 4: Gọi hàm lần 4

So sánh 4 và 3. Chọn list2.
Giữ lại: Nút 3.
Việc cần làm: Chờ kết quả của merge([4], [4]).

Bước 5: Gọi hàm lần 5

So sánh 4 và 4. Chọn list1.
Giữ lại: Nút 4.
Việc cần làm: Chờ kết quả của merge(nullptr, [4]).

Bước 6: Điều kiện dừng (Base Case)

Lúc này list1 là nullptr. Theo code: if (!list1) return list2;
Hàm trả về toàn bộ phần còn lại của list2, đó là nút [4].

Quá trình "Quay lui" (Backtracking) - Nối các mắt xích

Đây là lúc các "mắt xích" được nối lại với nhau khi hàm thoát ra khỏi ngăn xếp:

Hàm 5 nhận về [4]: Nối nút 4 (đang giữ) vào 4 mới nhận => [4, 4]. Trả về cho hàm 4.
Hàm 4 nhận về [4, 4]: Nối nút 3 (đang giữ) vào => [3, 4, 4]. Trả về cho hàm 3.
Hàm 3 nhận về [3, 4, 4]: Nối nút 2 (đang giữ) vào => [2, 3, 4, 4]. Trả về cho hàm 2.
Hàm 2 nhận về [2, 3, 4, 4]: Nối nút 1 (đang giữ) vào => [1, 2, 3, 4, 4]. Trả về cho hàm 1.
Hàm 1 nhận về [1, 2, 3, 4, 4]: Nối nút 1 (đang giữ) vào => [1, 1, 2, 3, 4, 4].

Kết quả cuối cùng: [1, 1, 2, 3, 4, 4]

So sánh trực quan

Vòng lặp (Iterative): Đ1ứng ở hiện tại, nhìn về phía trước và nối từng nút một vào đuôi.
Đệ quy (Recursive): Đi sâu vào tận cùng của danh sách trước, sau đó mới nối ngược từ đuôi lên đầu trên đường quay về.

Ưu và nhược điểm của Đệ quy:

Ưu: Code cực kỳ ngắn gọn và sạch sẽ (chỉ khoảng 5-6 dòng).
Nhược: Nếu danh sách cực kỳ dài (ví dụ 10,000 nút), nó có thể gây ra lỗi Stack Overflow vì máy tính phải ghi nhớ quá nhiều hàm đang chờ. Tuy nhiên, với giới hạn 50 nút của bài này, đệ quy chạy rất ổn!

Smart Pointers (unique_ptr) trong C++:

Trong C++ hiện đại (từ C++11 trở đi), việc quản lý bộ nhớ thủ công bằng new và delete thường được thay thế bằng Smart Pointers (Con trỏ thông minh). Phổ biến nhất là std::unique_ptr.

Tuy nhiên, có một "lời cảnh báo" nhỏ: Với cấu trúc dữ liệu ListNode chuẩn của LeetCode (dùng con trỏ thô *), chúng ta không thể chuyển đổi trực tiếp mà phải định nghĩa lại cấu trúc. Nhưng đây là cách tuyệt vời để bạn hiểu tư duy lập trình C++ chuyên nghiệp.

1. Định nghĩa lại Cấu trúc với `unique_ptr`

Thay vì dùng ListNode* next, chúng ta dùng std::unique_ptr<ListNode> next. Điều này có nghĩa là mỗi nút sẽ sở hữu duy nhất nút tiếp theo. Khi nút cha bị xóa, nút con sẽ tự động bị xóa theo.

C++

#include <memory>

struct ListNode {
    int val;
    std::unique_ptr<ListNode> next;

    ListNode(int x) : val(x), next(nullptr) {}
};

2. Logic trộn danh sách với Smart Pointers

Sự khác biệt lớn nhất ở đây là khái niệm Ownership (Quyền sở hữu). Bạn không thể chỉ đơn giản là gán con trỏ, bạn phải di chuyển (std::move) quyền sở hữu từ danh sách này sang danh sách khác.

C++

class Solution {
public:
    std::unique_ptr<ListNode> mergeTwoLists(std::unique_ptr<ListNode> l1, std::unique_ptr<ListNode> l2) {
        // Tạo nút giả trên Stack
        ListNode dummy(0);
        ListNode* tail = &dummy;

        while (l1 && l2) {
            if (l1->val <= l2->val) {
                // Di chuyển quyền sở hữu từ l1 sang tail->next
                tail->next = std::move(l1);
                // Lấy lại l1 từ vị trí mới để tiếp tục vòng lặp
                l1 = std::move(tail->next->next);
            } else {
                tail->next = std::move(l2);
                l2 = std::move(tail->next->next);
            }
            tail = tail->next.get(); // .get() để lấy con trỏ thô để duyệt (không chiếm quyền sở hữu)
        }

        // Nối phần còn dư
        if (l1) tail->next = std::move(l1);
        else if (l2) tail->next = std::move(l2);

        return std::move(dummy.next);
    }
};

3. Tại sao cách này lại "đỉnh"?

Không bao giờ Memory Leak: Khi biến dummy ra khỏi phạm vi hàm hoặc danh sách kết quả bị hủy, toàn bộ các nút sẽ được giải phóng tự động theo hiệu ứng Domino. Bạn không cần viết một dòng delete nào.
An toàn tuyệt đối: Bạn không thể vô tình dùng một con trỏ đã bị xóa, vì std::move sẽ đặt con trỏ cũ về nullptr.
Tư duy hiện đại: Đây là cách các hệ thống lớn (như trình duyệt Chrome hay hệ điều hành) quản lý tài nguyên để tránh lỗi bảo mật.

Một nhược điểm thực tế cần lưu ý

Với unique_ptr trong Danh sách liên kết, nếu danh sách quá dài (ví dụ 1 triệu nút), việc hủy danh sách sẽ gây ra đệ quy giải phóng (destructor gọi destructor) làm tràn bộ nhớ Stack. Trong thực tế, với danh sách cực lớn, người ta vẫn phải dùng vòng lặp để giải phóng thủ công hoặc dùng std::shared_ptr.

Sự khác biệt giữa get() và move():

move(): Chuyển toàn bộ "quyền sở hữu" căn nhà cho người khác. Bạn không còn chìa khóa nữa.
get(): Chỉ cho người khác "mượn chìa khóa" để vào xem nhà, nhưng bạn vẫn là chủ.