C++程序 平铺链表
给定一个链表,其中每个节点都代表一个链表,并包含其类型的两个指针:
- 链表中下一个节点的指针(下面的代码中称为‘right’指针)。
- 指向这个节点所指向的链表的指针(下面的代码中称为‘down’指针)。
所有的链表都是已排序的。请看下面的例子
5 -> 10 -> 19 -> 28
| | | |
V V V V
7 20 22 35
| | |
V V V
8 50 40
| |
V V
30 45
编写一个函数flatten()将这些链表压成一个单链表。被压缩的链表也应该是已排序的。例如,针对上面的输入列表,输出列表应该是5->7->8->10->19->20->22->28->30->35->40->45->50。
思路是使用链表归并排序的merge()过程。我们使用merge()一次次地将列表合并。我们递归地将当前列表与已经压平的列表merge()。
down指针用于连接被压缩的链表的节点。
下面是以上方法的实施:
// C++ program for flattening a
// Linked List
#include <bits/stdc++.h>
using namespace std;
// Link list node
class Node
{
public:
int data;
Node *right, *down;
};
Node* head = NULL;
// An utility function to merge
// two sorted linked lists
Node* merge(Node* a, Node* b)
{
// If first linked list is empty
// then second is the answer
if (a == NULL)
return b;
// If second linked list is empty
// then first is the result
if (b == NULL)
return a;
// Compare the data members of the
// two linked lists and put the larger
// one in the result
Node* result;
if (a->data < b->data)
{
result = a;
result->down = merge(a->down, b);
}
else
{
result = b;
result->down = merge(a, b->down);
}
result->right = NULL;
return result;
}
Node* flatten(Node* root)
{
// Base Cases
if (root == NULL ||
root->right == NULL)
return root;
// Recur for list on right
root->right = flatten(root->right);
// Now merge
root = merge(root, root->right);
// Return the root
// It will be in turn merged
// with its left
return root;
}
// Utility function to insert a node at
// beginning of the linked list
Node* push(Node* head_ref, int data)
{
// Allocate the Node &
// Put in the data
Node* new_node = new Node();
new_node->data = data;
new_node->right = NULL;
// Make next of new Node as head
new_node->down = head_ref;
// Move the head to point to
// new Node
head_ref = new_node;
return head_ref;
}
void printList()
{
Node* temp = head;
while (temp != NULL)
{
cout << temp->data << " ";
temp = temp->down;
}
cout << endl;
}
// Driver code
int main()
{
/* Create the following linked list
5 -> 10 -> 19 -> 28
| | | |
V V V V
7 20 22 35
| | |
V V V
8 50 40
| |
V V
30 45
*/
head = push(head, 30);
head = push(head, 8);
head = push(head, 7);
head = push(head, 5);
head->right = push(head->right, 20);
head->right = push(head->right, 10);
head->right->right =
push(head->right->right, 50);
head->right->right =
push(head->right->right, 22);
head->right->right =
push(head->right->right, 19);
head->right->right->right =
push(head->right->right->right, 45);
head->right->right->right =
push(head->right->right->right, 40);
head->right->right->right =
push(head->right->right->right, 35);
head->right->right->right =
push(head->right->right->right, 20);
// Flatten the list
head = flatten(head);
printList();
return 0;
}
// This code is contributed by rajsanghavi9.```
输出:
5 7 8 10 19 20 20 22 30 35 40 45 50
时间复杂度: O(NNM)-其中N为主链表中的节点数(可用右指针访问),M为单个子链表中的节点数(可用下指针访问)。
空间复杂度: O(N*M),因为递归函数将使用等于列表中所有元素的递归堆栈的大小。