ในปัญหานี้ เราได้รับรายการลิงก์ที่ประกอบด้วยโหนดพอยน์เตอร์ 2 โหนด ด้านขวาและด้านล่าง
-
โหนดขวา เป็นตัวชี้รายการลิงก์หลัก
-
โหนดล่าง ใช้สำหรับรายการลิงก์รองที่ขึ้นต้นด้วยโหนดนั้น
รายการที่เชื่อมโยงทั้งหมดจะถูกจัดเรียง
งานของเราคือการสร้างโปรแกรมเพื่อทำให้รายการเชื่อมโยงเรียบ และรายการผลลัพธ์จะเป็นรายการที่เรียงลำดับเอง
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
ป้อนข้อมูล
ผลผลิต
1-> 9-> 8 -> 4 -> 6-> 7-> 2-> 3-> 5
แนวทางการแก้ปัญหา
วิธีแก้ไขปัญหาคือการใช้ การเรียงลำดับการผสานสำหรับรายการที่เชื่อมโยง . วิธีนี้จะผสานรายการแบบเรียกซ้ำในลำดับที่จัดเรียงเพื่อสร้างรายการแบบเรียบ
ตัวอย่าง
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
#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;
} ผลลัพธ์
The Flattened Linked list is : 1 => 4 => 5 => 6 => 7 => 8 => 11 => 12 => 16 => NULL
