資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟
心理學
社會學
時尚研究
法學使用 C++ 展平連結串列
在這個問題中，我們提供了一個由兩個指標節點組成的連結串列，即右和下。
右節點是主連結串列指標。
下節點用於以該節點開頭的輔助連結串列。
所有連結串列都已排序。
我們的任務是建立一個程式來展平連結串列，結果列表本身也是一個已排序的列表。
讓我們舉個例子來理解這個問題
輸入
輸出
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
更新於：2022 年 2 月 1 日
378 次瀏覽
廣告