给定一个链表，其中每个节点代表一个链表，并包含其类型的两个指针： （i） 指向主列表中下一个节点的指针（在下面的代码中我们称之为“右”指针） （ii）指向该节点所在的链表的指针（在下面的代码中，我们称之为“向下”指针）。 所有链接列表都已排序。请参见下面的示例
null
5 -> 10 -> 19 -> 28 | | | | V V V V 7 20 22 35 | | | V V V 8 50 40 | | V V 30 45
编写一个函数flatte（），将列表展平为单个链接列表。展平的链表也应该进行排序。例如，对于上面的输入列表，输出列表应该是5->7->8->10->19->20->22->28->30->35->40->45->50。
其思想是使用 对链表进行合并排序。 我们使用merge（）逐个合并列表。我们递归地将（）当前列表与已展平的列表合并。 向下指针用于链接展开列表的节点。
以下是上述方法的实施情况：
C++
// 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() { /* Let us 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. |
JAVA
// Java program for flattening a Linked List class LinkedList { Node head; // head of list /* Linked list Node*/ class Node { int data; Node right, down; Node( int data) { this .data = data; right = null ; down = 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) { /* 1 & 2: Allocate the Node & Put in the data*/ Node new_node = new Node(data); /* 3. Make next of new Node as head */ new_node.down = head_ref; /* 4. Move the head to point to new Node */ head_ref = new_node; /*5. return to link it back */ return head_ref; } void printList() { Node temp = head; while (temp != null ) { System.out.print(temp.data + " " ); temp = temp.down; } System.out.println(); } /* Driver program to test above functions */ public static void main(String args[]) { LinkedList L = new LinkedList(); /* Let us 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 */ L.head = L.push(L.head, 30 ); L.head = L.push(L.head, 8 ); L.head = L.push(L.head, 7 ); L.head = L.push(L.head, 5 ); L.head.right = L.push(L.head.right, 20 ); L.head.right = L.push(L.head.right, 10 ); L.head.right.right = L.push(L.head.right.right, 50 ); L.head.right.right = L.push(L.head.right.right, 22 ); L.head.right.right = L.push(L.head.right.right, 19 ); L.head.right.right.right = L.push(L.head.right.right.right, 45 ); L.head.right.right.right = L.push(L.head.right.right.right, 40 ); L.head.right.right.right = L.push(L.head.right.right.right, 35 ); L.head.right.right.right = L.push(L.head.right.right.right, 20 ); // flatten the list L.head = L.flatten(L.head); L.printList(); } } /* This code is contributed by Rajat Mishra */ |
Python3
# Python program for flattening a Linked List class Node(): def __init__( self ,data): self .data = data self .right = None self .down = None class LinkedList(): def __init__( self ): # head of list self .head = None # Utility function to insert a node at beginning of the # linked list def push( self ,head_ref,data): # 1 & 2: Allocate the Node & # Put in the data new_node = Node(data) # Make next of new Node as head new_node.down = head_ref # 4. Move the head to point to new Node head_ref = new_node # 5. return to link it back return head_ref def printList( self ): temp = self .head while (temp ! = None ): print (temp.data,end = " " ) temp = temp.down print () # An utility function to merge two sorted linked lists def merge( self , a, b): # if first linked list is empty then second # is the answer if (a = = None ): return b # if second linked list is empty then first # is the result if (b = = None ): return a # compare the data members of the two linked lists # and put the larger one in the result result = None if (a.data < b.data): result = a result.down = self .merge(a.down,b) else : result = b result.down = self .merge(a,b.down) result.right = None return result def flatten( self , root): # Base Case if (root = = None or root.right = = None ): return root # recur for list on right root.right = self .flatten(root.right) # now merge root = self .merge(root, root.right) # return the root # it will be in turn merged with its left return root # Driver program to test above functions L = LinkedList() ''' Let us 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 ''' L.head = L.push(L.head, 30 ); L.head = L.push(L.head, 8 ); L.head = L.push(L.head, 7 ); L.head = L.push(L.head, 5 ); L.head.right = L.push(L.head.right, 20 ); L.head.right = L.push(L.head.right, 10 ); L.head.right.right = L.push(L.head.right.right, 50 ); L.head.right.right = L.push(L.head.right.right, 22 ); L.head.right.right = L.push(L.head.right.right, 19 ); L.head.right.right.right = L.push(L.head.right.right.right, 45 ); L.head.right.right.right = L.push(L.head.right.right.right, 40 ); L.head.right.right.right = L.push(L.head.right.right.right, 35 ); L.head.right.right.right = L.push(L.head.right.right.right, 20 ); # flatten the list L.head = L.flatten(L.head); L.printList() # This code is contributed by maheshwaripiyush9 |
C#
// C# program for flattening a Linked List using System; public class List { Node head; // head of list /* Linked list Node */ public class Node { public int data; public Node right, down; public Node( int data) { this .data = data; right = null ; down = 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) { /* * 1 & 2: Allocate the Node & Put in the data */ Node new_node = new Node(data); /* 3. Make next of new Node as head */ new_node.down = head_ref; /* 4. Move the head to point to new Node */ head_ref = new_node; /* 5. return to link it back */ return head_ref; } void printList() { Node temp = head; while (temp != null ) { Console.Write(temp.data + " " ); temp = temp.down; } Console.WriteLine(); } /* Driver program to test above functions */ public static void Main(String []args) { List L = new List(); /* * Let us 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 */ L.head = L.Push(L.head, 30); L.head = L.Push(L.head, 8); L.head = L.Push(L.head, 7); L.head = L.Push(L.head, 5); L.head.right = L.Push(L.head.right, 20); L.head.right = L.Push(L.head.right, 10); L.head.right.right = L.Push(L.head.right.right, 50); L.head.right.right = L.Push(L.head.right.right, 22); L.head.right.right = L.Push(L.head.right.right, 19); L.head.right.right.right = L.Push(L.head.right.right.right, 45); L.head.right.right.right = L.Push(L.head.right.right.right, 40); L.head.right.right.right = L.Push(L.head.right.right.right, 35); L.head.right.right.right = L.Push(L.head.right.right.right, 20); // flatten the list L.head = L.flatten(L.head); L.printList(); } } // This code is contributed by umadevi9616 |
Javascript
<script> // javascript program for flattening a Linked List var head; // head of list /* Linked list Node */ class Node { constructor(val) { this .data = val; this .down = null ; this .next = null ; } } // An utility function to merge two sorted linked lists function merge(a, 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 var 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; } function flatten(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 */ function push(head_ref , data) { /* * 1 & 2: Allocate the Node & Put in the data */ var new_node = new Node(data); /* 3. Make next of new Node as head */ new_node.down = head_ref; /* 4. Move the head to point to new Node */ head_ref = new_node; /* 5. return to link it back */ return head_ref; } function printList() { var temp = head; while (temp != null ) { document.write(temp.data + " " ); temp = temp.down; } document.write(); } /* Driver program to test above functions */ /* * Let us 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(); // This code contributed by aashish1995 </script> |
输出：
5 7 8 10 19 20 20 22 30 35 40 45 50
时间复杂性： O（N*N*M）–其中N是主链表中的节点数（可使用右指针访问），M是单个子链表中的节点数（可使用下指针访问）。
解释： 当我们一次合并两个列表时，
- 添加前两个列表后，所需时间为O（M+M）=O（2M）。
- 然后我们将另一个列表合并到上面合并的列表->时间=O（2M+M）=O（3M）。
- 然后我们将合并另一个列表->时间=O（3M+M）。
- 我们将继续将列表合并到以前合并的列表，直到所有列表合并。
- 所需总时间为O（2M+3M+4M+…N*M）=（2+3+4+…+N）*M
- 使用算术和公式：时间=O（（N*N+N-2）*M/2）
- 上述表达式大致等于 O（N*N*M） 对于N的大值
空间复杂性： O（N*M）——因为递归。递归函数将使用递归堆栈，其大小等于列表中元素的总数，即N*M。
练习： 可以使用优先级队列/min堆优化上述方法。然后时间复杂度为O（N*M*Log（N）），空间复杂度为O（N）。
如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
