Làm phẳng danh sách liên kết (Flattening Linked List) trong C++

Cho danh sách liên kết có hai con trỏ: right (danh sách chính) và down (danh sách phụ). Tất cả các danh sách đều đã sắp xếp. Nhiệm vụ: làm phẳng danh sách liên kết thành một danh sách đơn đã sắp xếp.

Ví dụ minh họa

Input: Danh sách đa cấp (hình ảnh)

Output: 1 → 4 → 5 → 6 → 7 → 8 → 11 → 12 → 16 → NULL

Phương pháp giải

Sử dụng Merge Sort cho danh sách liên kết. Đệ quy gộp các danh sách theo thứ tự đã sắp xếp.

Ví dụ chương trình

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

class Node{
public:
    int data;
    Node *right, *down;
};

Node* mergeList(Node* a, Node* b){
    if (!a) return b;
    if (!b) return a;
    Node* result;
    if (a->data < b->data){
        result = a;
        result->down = mergeList(a->down, b);
    } else {
        result = b;
        result->down = mergeList(a, b->down);
    }
    result->right = NULL;
    return result;
}

Node* flattenLinkedList(Node* root){
    if (!root || !root->right) return root;
    root->right = flattenLinkedList(root->right);
    root = mergeList(root, root->right);
    return root;
}

Node* push(Node* head_ref, int data){
    Node* new_node = new Node();
    new_node->data = data;
    new_node->right = NULL;
    new_node->down = head_ref;
    head_ref = new_node;
    return head_ref;
}

int main(){
    Node* head = NULL;
    head = push(head, 7);
    head = push(head, 1);
    head->right = push(head->right, 11);
    head->right = push(head->right, 5);
    head->right = push(head->right, 4);
    head->right->right = push(head->right->right, 12);
    head->right->right = push(head->right->right, 6);
    head->right->right->right = push(head->right->right->right, 8);
    head->right->right->right->right = push(head->right->right->right->right, 16);
    head = flattenLinkedList(head);
    cout << "Danh sách liên kết đã làm phẳng: \n";
    Node* temp = head;
    while (temp){
        cout << temp->data << " => ";
        temp = temp->down;
    }
    cout << "NULL";
    return 0;
}

Kết quả

Danh sách liên kết đã làm phẳng: 1 => 4 => 5 => 6 => 7 => 8 => 11 => 12 => 16 => NULL