Trong vấn đề này, chúng tôi được cung cấp danh sách liên kết bao gồm hai nút con trỏ, phải và xuống.
-
Nút bên phải là con trỏ danh sách được liên kết chính.
-
Nút xuống dành cho danh sách được liên kết phụ bắt đầu bằng nút đó.
Tất cả các danh sách được liên kết đều được sắp xếp.
Nhiệm vụ của chúng tôi là tạo một chương trình để làm phẳng một danh sách được liên kết và danh sách kết quả sẽ tự nó là một danh sách được sắp xếp.
Hãy lấy một ví dụ để hiểu vấn đề
Đầu vào
Đầu ra
1-> 9-> 8 -> 4 -> 6-> 7-> 2-> 3-> 5
Phương pháp tiếp cận giải pháp
Giải pháp cho vấn đề là sử dụng sắp xếp hợp nhất cho danh sách được liên kết . Phương pháp này sẽ hợp nhất các danh sách một cách đệ quy theo thứ tự đã sắp xếp để tạo thành một danh sách phẳng.
Ví dụ
Chương trình minh họa hoạt động của giải pháp của chúng tôi
#include <bits/stdc++.h>
using namespace std;
class Node{
public:
int data;
Node *right, *down;
};
Node* head = NULL;
Node* mergeList(Node* a, Node* b){
if (a == NULL)
return b;
if (b == NULL)
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 == NULL || root->right == NULL)
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(){
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<<"The Flattened Linked list is : \n";
Node* temp = head;
while (temp != NULL){
cout<<temp->data<<" => ";
temp = temp->down;
}
cout<<"NULL";
return 0;
} Đầu ra
The Flattened Linked list is : 1 => 4 => 5 => 6 => 7 => 8 => 11 => 12 => 16 => NULL