Chia danh sách liên kết theo tỷ lệ p:q trong C++

Giới thiệu

Chia một danh sách liên kết đơn thành hai phần với tỷ lệ p:q. Phần đầu có p node, phần sau có q node.

Ví dụ

Danh sách: 1 → 2 → 3 → 4 → 5 → 6 (6 node)

Tỷ lệ p:q = 2:4

Kết quả: Phần 1: 1 → 2 | Phần 2: 3 → 4 → 5 → 6

Mã nguồn hoàn chỉnh

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int data;
    Node *next;
    Node(int data) {
        this->data = data;
        this->next = NULL;
    }
};

void printLinkedList(Node* head) {
    Node *temp = head;
    while (temp) {
        cout << temp->data << " -> ";
        temp = temp->next;
    }
    cout << "NULL" << endl;
}

void splitLinkedList(Node *head, int p, int q) {
    int n = 0;
    Node *temp = head;
    
    // Tìm độ dài danh sách
    while (temp != NULL) {
        n += 1;
        temp = temp->next;
    }
    
    // Kiểm tra khả thi
    if (p + q > n) {
        cout << "Khong the chia danh sach lien ket" << endl;
        return;
    }
    
    // Di chuyển đến node thứ p
    temp = head;
    while (p > 1) {
        temp = temp->next;
        p -= 1;
    }
    
    // Tách danh sách
    Node *head_two = temp->next;
    temp->next = NULL;
    
    // In kết quả
    printLinkedList(head);
    printLinkedList(head_two);
}

int main() {
    Node* head = new Node(1);
    head->next = new Node(2);
    head->next->next = new Node(3);
    head->next->next->next = new Node(4);
    head->next->next->next->next = new Node(5);
    head->next->next->next->next->next = new Node(6);
    
    int p = 2, q = 4;
    splitLinkedList(head, p, q);
    
    return 0;
}

Kết quả chạy chương trình

1 -> 2 -> NULL
3 -> 4 -> 5 -> 6 -> NULL

Phân tích độ phức tạp

• Thời gian: O(n) - duyệt danh sách 2 lần (đếm độ dài + tìm vị trí tách)
• Không gian: O(1) - chỉ dùng con trỏ, không cấp phát bộ nhớ mới

Các trường hợp đặc biệt

• p + q > n: Không thể chia, in thông báo lỗi
• p = 0: Phần đầu rỗng, toàn bộ thuộc phần sau
• q = 0: Phần sau rỗng, toàn bộ thuộc phần đầu
• p + q < n: Chỉ chia phần đầu p+q node, phần còn lại bị bỏ qua

Cải tiến: Chia chính xác tỷ lệ

Nếu muốn chia theo tỷ lệ phần trăm (ví dụ 30% - 70%):

void splitByRatio(Node* head, double ratio) {
    int n = 0;
    Node* temp = head;
    while (temp) { n++; temp = temp->next; }
    
    int p = round(n * ratio);
    int q = n - p;
    splitLinkedList(head, p, q);
}

Kết luận

Kỹ thuật tách danh sách liên kết bằng cách điều chỉnh con trỏ next là thao tác cơ bản, thường dùng trong sắp xếp (merge sort), xử lý luồng dữ liệu, v.v.