Chương 04

Kỹ Thuật Sắp Xếp Trên
Danh Sách Liên Kết Đơn

Trên Linked List, bạn không thể hoán đổi giá trị — mọi thao tác đều phải thông qua thay đổi hướng con trỏ. Đây là thử thách thực sự cho tư duy thuật toán.

🔗 Cấu trúc Node & Nguyên tắc Con trỏ

Mỗi node trong danh sách liên kết đơn chứa 2 thành phần: data (giá trị) và next (con trỏ đến node tiếp theo).

⚡ C++ — Cấu trúc Node

struct Node {
    int data;
    Node* next;

    Node(int val) : data(val), next(nullptr) {}
};

// Tạo danh sách liên kết từ mảng
Node* createList(vector<int>& arr) {
    if (arr.empty()) return nullptr;
    Node* head = new Node(arr[0]);
    Node* curr = head;
    for (int i = 1; i < arr.size(); i++) {
        curr->next = new Node(arr[i]);
        curr = curr->next;
    }
    return head;
}

// In danh sách liên kết
void printList(Node* head) {
    while (head) {
        cout << head->data;
        if (head->next) cout << " -> ";
        head = head->next;
    }
    cout << " -> NULL" << endl;
}

❌ Nguyên tắc vàng

Trên Linked List, KHÔNG hoán đổi giá trị (data) giữa các node. Thay vào đó, ta thay đổi hướng con trỏ next để "di chuyển" node đến vị trí mới. Đây là điểm khác biệt cốt lõi so với sắp xếp trên mảng!

🔄 Minh họa: Thay đổi hướng con trỏ

Muốn chèn node 5 vào giữa 3 → 8:

→

5
→

chèn vào

→

NULL

Chỉ cần: newNode->next = curr->next; curr->next = newNode;

🐢🐇 Kỹ thuật "Con trỏ Rùa và Thỏ"

Kỹ thuật dùng 2 con trỏ di chuyển với tốc độ khác nhau để tìm điểm giữa danh sách trong một lần duyệt duy nhất.

Nguyên lý hoạt động

slow (🐢): mỗi bước đi 1 node
fast (🐇): mỗi bước đi 2 nodes
Khi fast đến cuối → slow đang ở giữa danh sách!

🎯 Minh họa trực quan

→

🐢 slow

→

🐇 fast

NULL

fast đã gần cuối → slow đang ở giữa (node 8)

⚡ C++ — Tìm điểm giữa

// Tìm node ở giữa danh sách liên kết
Node* getMiddle(Node* head) {
    if (!head) return head;

    Node* slow = head;
    Node* fast = head->next;  // fast bắt đầu từ head->next

    while (fast && fast->next) {
        slow = slow->next;       // Đi 1 bước
        fast = fast->next->next; // Đi 2 bước
    }

    return slow;  // slow giờ ở giữa
}

📥 Insertion Sort trên Linked List

Ý tưởng giống Insertion Sort trên mảng, nhưng thay vì dịch phần tử, ta tháo node ra và chèn lại vào đúng vị trí trong phần đã sắp xếp.

⚡ C++ — Insertion Sort (Linked List)

Node* insertionSortList(Node* head) {
    if (!head || !head->next) return head;

    Node* sorted = nullptr;  // Danh sách đã sắp xếp (ban đầu rỗng)

    Node* curr = head;
    while (curr) {
        Node* next = curr->next;  // Lưu node tiếp theo

        // Chèn curr vào đúng vị trí trong sorted
        if (!sorted || sorted->data >= curr->data) {
            // Chèn vào đầu
            curr->next = sorted;
            sorted = curr;
        } else {
            // Tìm vị trí chèn
            Node* temp = sorted;
            while (temp->next && temp->next->data < curr->data) {
                temp = temp->next;
            }
            curr->next = temp->next;
            temp->next = curr;
        }

        curr = next;
    }

    return sorted;
}

// Sử dụng:
// head = insertionSortList(head);

💡 Phân tích

Time: O(n²) worst/average, O(n) best (đã sắp xếp)
Space: O(1) — chỉ thay đổi con trỏ, không tạo node mới
Stable: ✅ Có (dùng < thay vì <= khi tìm vị trí)

🔀 Merge Sort cho Linked List — O(N log N) với O(1) Space

Đây là giải pháp tối ưu nhất để sắp xếp Linked List. Khác với mảng (cần O(n) temp), Merge Sort trên LL chỉ cần O(1) bộ nhớ phụ vì ta chỉ thay đổi con trỏ!

🧠 Ba bước cốt lõi

Split: Dùng Slow/Fast pointer để tách list thành 2 nửa
Recurse: Đệ quy sắp xếp từng nửa
Merge: Trộn 2 list đã sắp xếp bằng cách thay đổi con trỏ next

⚡ C++ — Merge Sort (Linked List)

// Trộn 2 danh sách đã sắp xếp
Node* mergeTwoLists(Node* l1, Node* l2) {
    Node dummy(0);       // Dummy node làm đầu mối
    Node* tail = &dummy;

    while (l1 && l2) {
        if (l1->data <= l2->data) {   // <= để stable
            tail->next = l1;
            l1 = l1->next;
        } else {
            tail->next = l2;
            l2 = l2->next;
        }
        tail = tail->next;
    }
    tail->next = l1 ? l1 : l2;

    return dummy.next;
}

// Merge Sort cho Linked List
Node* mergeSort(Node* head) {
    // Base case: 0 hoặc 1 node
    if (!head || !head->next) return head;

    // Bước 1: Tìm giữa và tách thành 2 nửa
    Node* mid = getMiddle(head);
    Node* rightHalf = mid->next;
    mid->next = nullptr;  // Cắt đôi!

    // Bước 2: Đệ quy sắp xếp
    Node* left = mergeSort(head);
    Node* right = mergeSort(rightHalf);

    // Bước 3: Trộn
    return mergeTwoLists(left, right);
}

// Sử dụng:
// head = mergeSort(head);

💡 Tại sao Merge Sort là "vua" trên Linked List?

• O(n log n) guaranteed — không worst case
• O(1) extra space — không cần mảng phụ, chỉ thay đổi con trỏ
• Stable — giữ thứ tự phần tử bằng nhau
• QuickSort kém hiệu quả trên LL vì không thể truy cập ngẫu nhiên (partition khó)

Thuật toán trên LL	Time	Space	Stable
Insertion Sort	O(n²)	O(1)	✅
Merge Sort	O(n log n)	O(1)*	✅

* O(log n) cho call stack đệ quy, nhưng không cần mảng phụ O(n) như trên mảng

← Chương 3: Sắp Xếp Nâng Cao Chương 5: Bài Toán Ứng Dụng →