Merge K sorted Doubly Linked List in Sorted Order
Given K sorted doubly linked list. The task is to merge all sorted doubly linked list in single sorted doubly linked list means final list must be sorted.
Examples:
Input:
List 1 : 2 <-> 7 <-> 8 <-> 12 <-> 15 <-> NULL
List 2 : 4 <-> 9 <-> 10 <-> NULL
List 3 : 5 <-> 9 <-> 11 <-> 16 <-> NULL
Output: 2 4 5 7 8 9 9 10 11 12 15 16
Input:
List 1 : 4 <-> 7 <-> 8 <-> 10 <-> NULL
List 2 : 4 <-> 19 <-> 20 <-> 23 <-> 27 <-> NULL
List 3 : 3 <-> 9 <-> 12 <-> 20 <-> NULL
List 4 : 1 <-> 19 <-> 22 <-> NULL
List 5 : 7 <-> 16 <-> 20 <-> 21 <-> NULL
Output :
1 3 4 4 7 7 8 9 10 12 16 19 19 20 20 20 21 22 23 27
Prerequisite: Reference-of-algorithm
Approach:
- First merge two doubly linked list in sorted order
- Then merge this list with another list in sorted order
- Do the same thing until all list are not merged
- Keep in mind that you have to merge two list at a time then merged list will be merged newly list
Algorithm:
function merge(A, B) is
inputs A, B : list
returns list
C := new empty list
while A is not empty and B is not empty do
if head(A) < head(B) then
append head(A) to C
drop the head of A
else
append head(B) to C
drop the head of B
// By now, either A or B is empty
// It remains to empty the other input list
while A is not empty do
append head(A) to C
drop the head of A
while B is not empty do
append head(B) to C
drop the head of B
return C
Below is the implementation of the above approach:
C++
// C++ program to merge K sorted doubly// linked list in sorted order#include <bits/stdc++.h>using namespace std;// A linked list nodestruct Node { int data; Node* next; Node* prev;};// Given a reference (pointer to pointer) to the head// Of a DLL and an int, appends a new node at the endvoid append(struct Node** head_ref, int new_data){ // Allocate node struct Node* new_node = (struct Node*)malloc(sizeof(struct Node)); struct Node* last = *head_ref; // Put in the data new_node->data = new_data; // This new node is going to be the last // node, so make next of it as NULL new_node->next = NULL; // If the Linked List is empty, then make // the new node as head */ if (*head_ref == NULL) { new_node->prev = NULL; *head_ref = new_node; return; } // Else traverse till the last node while (last->next != NULL) last = last->next; // Change the next of last node last->next = new_node; // Make last node as previous of new node new_node->prev = last; return;}// Function to print the listvoid printList(Node* node){ Node* last; // Run while loop unless node becomes null while (node != NULL) { cout << node->data << " "; last = node; node = node->next; }}// Function to merge two// sorted doubly linked listsNode* mergeList(Node* p, Node* q){ Node* s = NULL; // If any of the list is empty if (p == NULL || q == NULL) { return (p == NULL ? q : p); } // Comparison the data of two linked list if (p->data < q->data) { p->prev = s; s = p; p = p->next; } else { q->prev = s; s = q; q = q->next; } // Store head pointer before merge the list Node* head = s; while (p != NULL && q != NULL) { if (p->data < q->data) { // Changing of pointer between // Two list for merging s->next = p; p->prev = s; s = s->next; p = p->next; } else { // Changing of pointer between // Two list for merging s->next = q; q->prev = s; s = s->next; q = q->next; } } // Condition to check if any anyone list not end if (p == NULL) { s->next = q; q->prev = s; } if (q == NULL) { s->next = p; p->prev = s; } // Return head pointer of merged list return head;}// Function to merge all sorted linked// list in sorted orderNode* mergeAllList(Node* head[], int k){ Node* finalList = NULL; for (int i = 0; i < k; i++) { // Function call to merge two sorted // doubly linked list at a time finalList = mergeList(finalList, head[i]); } // Return final sorted doubly linked list return finalList;}// Driver codeint main(){ int k = 3; Node* head[k]; // Loop to initialize all the lists to empty for (int i = 0; i < k; i++) { head[i] = NULL; } // Create first doubly linked List // List1 -> 1 <=> 5 <=> 9 append(&head[0], 1); append(&head[0], 5); append(&head[0], 9); // Create second doubly linked List // List2 -> 2 <=> 3 <=> 7 <=> 12 append(&head[1], 2); append(&head[1], 3); append(&head[1], 7); append(&head[1], 12); // Create third doubly linked List // List3 -> 8 <=> 11 <=> 13 <=> 18 append(&head[2], 8); append(&head[2], 11); append(&head[2], 13); append(&head[2], 18); // Function call to merge all sorted // doubly linked lists in sorted order Node* finalList = mergeAllList(head, k); // Print final sorted list printList(finalList); return 0;} |
Java
// Java program to merge K sorted doubly// linked list in sorted orderclass GFG{ // A linked list nodestatic class Node { int data; Node next; Node prev;};// Given a reference (pointer to pointer) to the head// Of a DLL and an int, appends a new node at the endstatic Node append(Node head_ref, int new_data){ // Allocate node Node new_node = new Node(); Node last = head_ref; // Put in the data new_node.data = new_data; // This new node is going to be the last // node, so make next of it as null new_node.next = null; // If the Linked List is empty, then make // the new node as head */ if (head_ref == null) { new_node.prev = null; head_ref = new_node; return head_ref; } // Else traverse till the last node while (last.next != null) last = last.next; // Change the next of last node last.next = new_node; // Make last node as previous of new node new_node.prev = last; return head_ref;}// Function to print the liststatic void printList(Node node){ Node last; // Run while loop unless node becomes null while (node != null) { System.out.print( node.data + " "); last = node; node = node.next; }}// Function to merge two// sorted doubly linked listsstatic Node mergeList(Node p, Node q){ Node s = null; // If any of the list is empty if (p == null || q == null) { return (p == null ? q : p); } // Comparison the data of two linked list if (p.data < q.data) { p.prev = s; s = p; p = p.next; } else { q.prev = s; s = q; q = q.next; } // Store head pointer before merge the list Node head = s; while (p != null && q != null) { if (p.data < q.data) { // Changing of pointer between // Two list for merging s.next = p; p.prev = s; s = s.next; p = p.next; } else { // Changing of pointer between // Two list for merging s.next = q; q.prev = s; s = s.next; q = q.next; } } // Condition to check if any anyone list not end if (p == null) { s.next = q; q.prev = s; } if (q == null) { s.next = p; p.prev = s; } // Return head pointer of merged list return head;}// Function to merge all sorted linked// list in sorted orderstatic Node mergeAllList(Node head[], int k){ Node finalList = null; for (int i = 0; i < k; i++) { // Function call to merge two sorted // doubly linked list at a time finalList = mergeList(finalList, head[i]); } // Return final sorted doubly linked list return finalList;}// Driver codepublic static void main(String args[]){ int k = 3; Node head[] = new Node[k]; // Loop to initialize all the lists to empty for (int i = 0; i < k; i++) { head[i] = null; } // Create first doubly linked List // List1 . 1 <=> 5 <=> 9 head[0] = append(head[0], 1); head[0] = append(head[0], 5); head[0] = append(head[0], 9); // Create second doubly linked List // List2 . 2 <=> 3 <=> 7 <=> 12 head[1] = append(head[1], 2); head[1] = append(head[1], 3); head[1] = append(head[1], 7); head[1] = append(head[1], 12); // Create third doubly linked List // List3 . 8 <=> 11 <=> 13 <=> 18 head[2] = append(head[2], 8); head[2] = append(head[2], 11); head[2] = append(head[2], 13); head[2] = append(head[2], 18); // Function call to merge all sorted // doubly linked lists in sorted order Node finalList = mergeAllList(head, k); // Print final sorted list printList(finalList);}}// This code is contributed by Arnab Kundu |
Python
# Python program to merge K sorted doubly# linked list in sorted order# A linked list nodeclass Node: def __init__(self, new_data): self.data = new_data self.next = None self.prev = None# Given a reference (pointer to pointer) to the head# Of a DLL and an int, appends a new node at the enddef append(head_ref, new_data): # Allocate node new_node = Node(0) last = head_ref # Put in the data new_node.data = new_data # This new node is going to be the last # node, so make next of it as None new_node.next = None # If the Linked List is empty, then make # the new node as head */ if (head_ref == None) : new_node.prev = None head_ref = new_node return head_ref # Else traverse till the last node while (last.next != None): last = last.next # Change the next of last node last.next = new_node # Make last node as previous of new node new_node.prev = last return head_ref# Function to print the listdef printList(node): last = None # Run while loop unless node becomes None while (node != None) : print( node.data, end = " ") last = node node = node.next # Function to merge two# sorted doubly linked listsdef mergeList(p, q): s = None # If any of the list is empty if (p == None or q == None) : if (p == None ): return q else: return p # Comparison the data of two linked list if (p.data < q.data): p.prev = s s = p p = p.next else: q.prev = s s = q q = q.next # Store head pointer before merge the list head = s while (p != None and q != None) : if (p.data < q.data) : # Changing of pointer between # Two list for merging s.next = p p.prev = s s = s.next p = p.next else: # Changing of pointer between # Two list for merging s.next = q q.prev = s s = s.next q = q.next # Condition to check if any anyone list not end if (p == None): s.next = q q.prev = s if (q == None): s.next = p p.prev = s # Return head pointer of merged list return head# Function to merge all sorted linked# list in sorted orderdef mergeAllList(head,k): finalList = None i = 0 while ( i < k ) : # Function call to merge two sorted # doubly linked list at a time finalList = mergeList(finalList, head[i]) i = i + 1 # Return final sorted doubly linked list return finalList# Driver codek = 3head = [0] * ki = 0# Loop to initialize all the lists to emptywhile ( i < k ) : head[i] = None i = i + 1 # Create first doubly linked List# List1 . 1 <=> 5 <=> 9head[0] = append(head[0], 1)head[0] = append(head[0], 5)head[0] = append(head[0], 9)# Create second doubly linked List# List2 . 2 <=> 3 <=> 7 <=> 12head[1] = append(head[1], 2)head[1] = append(head[1], 3)head[1] = append(head[1], 7)head[1] = append(head[1], 12)# Create third doubly linked List# List3 . 8 <=> 11 <=> 13 <=> 18head[2] = append(head[2], 8)head[2] = append(head[2], 11)head[2] = append(head[2], 13)head[2] = append(head[2], 18)# Function call to merge all sorted# doubly linked lists in sorted orderfinalList = mergeAllList(head, k)# Print final sorted listprintList(finalList)# This code is contributed by Arnab Kundu |
C#
// C# program to merge K sorted doubly // linked list in sorted orderusing System;class GFG { // A linked list node public class Node { public int data; public Node next; public Node prev; }; // Given a reference (pointer to pointer) // to the head of a DLL and an int, // appends a new node at the end static Node append(Node head_ref, int new_data) { // Allocate node Node new_node = new Node(); Node last = head_ref; // Put in the data new_node.data = new_data; // This new node is going to be the last // node, so make next of it as null new_node.next = null; // If the Linked List is empty, // then make the new node as head */ if (head_ref == null) { new_node.prev = null; head_ref = new_node; return head_ref; } // Else traverse till the last node while (last.next != null) last = last.next; // Change the next of last node last.next = new_node; // Make last node as previous of new node new_node.prev = last; return head_ref; } // Function to print the list static void printList(Node node) { Node last; // Run while loop unless node becomes null while (node != null) { Console.Write(node.data + " "); last = node; node = node.next; } } // Function to merge two // sorted doubly linked lists static Node mergeList(Node p, Node q) { Node s = null; // If any of the list is empty if (p == null || q == null) { return (p == null ? q : p); } // Comparison the data of two linked list if (p.data < q.data) { p.prev = s; s = p; p = p.next; } else { q.prev = s; s = q; q = q.next; } // Store head pointer before merge the list Node head = s; while (p != null && q != null) { if (p.data < q.data) { // Changing of pointer between // Two list for merging s.next = p; p.prev = s; s = s.next; p = p.next; } else { // Changing of pointer between // Two list for merging s.next = q; q.prev = s; s = s.next; q = q.next; } } // Condition to check if // any anyone list not end if (p == null) { s.next = q; q.prev = s; } if (q == null) { s.next = p; p.prev = s; } // Return head pointer of merged list return head; } // Function to merge all sorted linked // list in sorted order static Node mergeAllList(Node []head, int k) { Node finalList = null; for (int i = 0; i < k; i++) { // Function call to merge two sorted // doubly linked list at a time finalList = mergeList(finalList, head[i]); } // Return final sorted doubly linked list return finalList; } // Driver code public static void Main() { int k = 3; Node []head = new Node[k]; // Loop to initialize all the lists to empty for (int i = 0; i < k; i++) { head[i] = null; } // Create first doubly linked List // List1 . 1 <=> 5 <=> 9 head[0] = append(head[0], 1); head[0] = append(head[0], 5); head[0] = append(head[0], 9); // Create second doubly linked List // List2 . 2 <=> 3 <=> 7 <=> 12 head[1] = append(head[1], 2); head[1] = append(head[1], 3); head[1] = append(head[1], 7); head[1] = append(head[1], 12); // Create third doubly linked List // List3 . 8 <=> 11 <=> 13 <=> 18 head[2] = append(head[2], 8); head[2] = append(head[2], 11); head[2] = append(head[2], 13); head[2] = append(head[2], 18); // Function call to merge all sorted // doubly linked lists in sorted order Node finalList = mergeAllList(head, k); // Print final sorted list printList(finalList); } }// This code is contributed by AnkitRai01 |
Javascript
<script>// javascript program to merge K sorted doubly// linked list in sorted order // A linked list node class Node { constructor(){ this.data = 0; this.next = null; this.prev = null; } } // Given a reference (pointer to pointer) to the head // Of a DLL and an int, appends a new node at the end function append( head_ref , new_data) { // Allocate node new_node = new Node(); last = head_ref; // Put in the data new_node.data = new_data; // This new node is going to be the last // node, so make next of it as null new_node.next = null; // If the Linked List is empty, then make // the new node as head */ if (head_ref == null) { new_node.prev = null; head_ref = new_node; return head_ref; } // Else traverse till the last node while (last.next != null) last = last.next; // Change the next of last node last.next = new_node; // Make last node as previous of new node new_node.prev = last; return head_ref; } // Function to print the list function printList( node) { last; // Run while loop unless node becomes null while (node != null) { document.write(node.data + " "); last = node; node = node.next; } } // Function to merge two // sorted doubly linked lists function mergeList( p, q) { s = null; // If any of the list is empty if (p == null || q == null) { return (p == null ? q : p); } // Comparison the data of two linked list if (p.data < q.data) { p.prev = s; s = p; p = p.next; } else { q.prev = s; s = q; q = q.next; } // Store head pointer before merge the list head = s; while (p != null && q != null) { if (p.data < q.data) { // Changing of pointer between // Two list for merging s.next = p; p.prev = s; s = s.next; p = p.next; } else { // Changing of pointer between // Two list for merging s.next = q; q.prev = s; s = s.next; q = q.next; } } // Condition to check if any anyone list not end if (p == null) { s.next = q; q.prev = s; } if (q == null) { s.next = p; p.prev = s; } // Return head pointer of merged list return head; } // Function to merge all sorted linked // list in sorted order function mergeAllList( head , k) { finalList = null; for (i = 0; i < k; i++) { // Function call to merge two sorted // doubly linked list at a time finalList = mergeList(finalList, head[i]); } // Return final sorted doubly linked list return finalList; } // Driver code var k = 3; head = Array(k).fill(null); // Loop to initialize all the lists to empty for (i = 0; i < k; i++) { head[i] = null; } // Create first doubly linked List // List1 . 1 <=> 5 <=> 9 head[0] = append(head[0], 1); head[0] = append(head[0], 5); head[0] = append(head[0], 9); // Create second doubly linked List // List2 . 2 <=> 3 <=> 7 <=> 12 head[1] = append(head[1], 2); head[1] = append(head[1], 3); head[1] = append(head[1], 7); head[1] = append(head[1], 12); // Create third doubly linked List // List3 . 8 <=> 11 <=> 13 <=> 18 head[2] = append(head[2], 8); head[2] = append(head[2], 11); head[2] = append(head[2], 13); head[2] = append(head[2], 18); // Function call to merge all sorted // doubly linked lists in sorted order finalList = mergeAllList(head, k); // Print final sorted list printList(finalList);// This code is contributed by umadevi9616</script> |
Output:
1 2 3 5 7 8 9 11 12 13 18
Time Complexity: O(N*k)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
