Merge K Sorted Doubly Linked List in Sorted Order

Last Updated on November 28, 2022 by Prepbytes

A doubly linked list is a type of linked list in which the node consists of three parts i.e. the data, the pointer of the previous node and the pointer of the next node.
In this article we will study how to sort k sorted doubly linked list. Let us have a look to the problem statement for a better understanding of how to sort k sorted doubly linked list.

How to sort k sorted doubly linked list

In this problem, we will be given K sorted doubly linked lists. We need to merge all lists such that the newly created doubly linked list is also in sorted order.

If you want to see how to merge K sorted singly-linked lists, check out these articles merge K sorted linked lists(set 1) and merge K sorted linked lists(set 2 – using Min heap).

The problem statement is quite straightforward, we will be given K doubly-linked lists that are sorted in nature, and then we need to form a doubly-linked list using the nodes of all the given linked lists such that the newly formed list is sorted in order.

Let’s try to understand the problem with the help of an example:
If the sorted doubly-linked lists given to us are:

• Then, according to the problem statement, we need to merge all these given linked lists into a single doubly linked list in such a way that after merging, the final list is also sorted in nature.
• The list that we need to return must contain all the nodes of all three given lists in sorted order.
• So, after merging, the newly formed sorted list will be:
  

At this point, we have understood the problem statement. Now we will try to formulate an approach for this problem.

Before moving to the approach section, try to think about how you can approach this problem.

• If stuck, no problem, we will thoroughly see how we can approach this problem in the next section.

Let’s move to the approach section.

Approach 1 of how to sort k sorted doubly linked list

• Initialize a result list with the first list.
• Traverse all K lists one by one, starting from the second list, and merge them with the initialized result list using the merge two sorted list concepts.
• At last, when we have traversed all the K lists, our result list will be containing all the nodes of the K lists in sorted order.
• Finally, we can return this result list as our output.

To see how to merge two sorted linked lists, check out this article.

Some Important Observations

• Every time we add a sorted list into our result list, its size increases by n.
• So, when we add the second list, the complexity is 2n. Then, on adding the third list, the complexity is 3n. Similarly, when we are adding the K^th list, the complexity is *Kn**.
  • So, the total complexity is (2n + 3n + 4n + ….. + Kn) = n ( 2+3+4+…+K), which is asymptotically equal to (n*K² ).

Time Complexity: O(n* K² ), n is the number of nodes in the list, and K is the total number of lists

Space Complexity: O(1)

We can observe that if the number of lists given is quite large, then the above approach will result in TLE. So, we need to reduce the time complexity, which is possible if we use the divide and conquer technique.

Approach 2 of how to sort k sorted doubly linked list

• In this approach, we merge the linked lists in pairs.
  • In the first iteration, we will have K/2 pairs so; we will merge them using the merge two sorted lists concept.
  • Then after the first iteration, we will have K/2 lists, i.e., K/4 pairs of lists to merge.
  • After each iteration, the number of lists to be merged will reduce by half of their previous count.
  • At last, we will be left with a single list which will contain all lists merged in sorted order.

## Algorithm of how to sort k sorted doubly linked list

1. Initialize a variable back with the last index of the array containing the head of all the lists.
2. Run a while loop till back is not equal to zero.
– Inside while loop, we need to merge pairs so, initialize two variables, i.e., i with 0 and j with back.
– Now, we need to run a while loop as long as i is less than j.
– Now merge i^th and j^th list and store it as an i^th element of the array.
– Now, increment i by one and decrement j by one.
– If i is greater than or equal to j, we need to update back by j.
3. After execution of both the while loops, we need to return the first element of the array.
4. In case you are not aware of how to merge two sorted linked lists, please check this article.

Dry Run of how to sort k sorted doubly linked list

## Code Implementation of how to sort k sorted doubly linked list

#include
using namespace std;

// class with constructor for a node of Linked list
class Node {
    public:
    int data;
    Node* next,*prev;
    // constructor
    Node(int x){
        data = x;
        next = NULL;
        prev = NULL;
    }
};

void add_at_begin(Node** head, int x)
{
 
    Node* new_node = new Node(x);//create node of doubly linked 
   //list
 
    //assign the data entered by user
    new_node->data = x;
 
    // node is inserted in beginning so, prev will always 
    // be NULL
    new_node->prev = NULL;
 
    //the node created is inserted at beginning so we need to
    //connect it with previous head
    new_node->next = (*head);
     
    // change the head to the current node’s address
    if ((*head) != NULL)
        (*head)->prev = new_node;
 
    (*head) = new_node;
}


// This function prints data of the linked list
void print(Node* head)
{
    Node* curr = head;
    while (curr != NULL) {
        cout << curr->data << " , ";
        curr = curr->next;
    }
    cout<<"NULL"<data < l2->data) {
            tail->next = l1;
            l1->prev = tail;
            l1 = l1->next;
        } else {
            tail->next = l2;
            l2->prev = tail;
            l2 = l2->next;
        }
        tail = tail->next;
    }

    //tail->next = l1 ? l1 : l2;
    if(l1 != NULL){
        tail->next = l1;
        l1->prev = tail;
    }else{
        tail->next = l2;
        l2->prev = tail;
    }
    return dummy.next;
}


// This function merges 'K' sorted lists into one sorted list
Node* mergeKLists(Node* arr[], int back)
{
    // run the while loop till 'back' is not equal to
    while (back != 0) {
        int i = 0, j = back;
 
        while (i < j) {
            // merge ith and jth list and store the list at
            // ith index of array
            arr[i] = mergeTwoLists(arr[i], arr[j]);
 
            // increment 'i' and decrement 'j' by one
            i++, j--;
 
            // update 'back' by 'j' once j is less than or
            // equal to 'i'
            if (i >= j)
                back = j;
        }
    }
 
    return arr[0];
}

// main function
int main()
{
    Node * arr[3];

    Node* h1 = NULL;
    add_at_begin(&h1, 5);
    add_at_begin(&h1, 3);
    add_at_begin(&h1, 2);
    cout<<"First linked list: ";
    print(h1);

    Node* h2 = NULL;
    add_at_begin(&h2, 8);
    add_at_begin(&h2, 4);
    add_at_begin(&h2, 1);
    cout<<"Second linked list: ";
    print(h2);

    Node* h3 = NULL;
    add_at_begin(&h3, 9);
    add_at_begin(&h3, 7);
    add_at_begin(&h3, 6);
    cout<<"Third linked list: ";
    print(h3);

    arr[0] = h1;
    arr[1] = h2;
    arr[2] = h3;
    
    cout<<"Final merged linked list: ";
    print(mergeKLists(arr,2));
    return 0;
}

Output
First linked list: 2 , 3 , 5 , NULL
Second linked list: 1 , 4 , 8 , NULL
Third linked list: 6 , 7 , 9 , NULL
Final merged linked list: 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , NULL

Time Complexity of how to sort k sorted doubly linked list : O( n K log(K) ), n is the number of nodes in the list and K is the total number of lists.

**Conclusion**

This blog taught the proper explanation and solution of how to sort k sorted doubly linked list in the most optimal way. We hope we will clear all your doubts regarding the problem and enhance your knowledge. Also, our experts have created some famous and interesting problems over the linked list. you can follow this link Linked List.

## FAQs regarding how to sort k sorted doubly linked list

**1. Are doubly linked lists sorted?**
Given a sorted doubly linked list and a value to insert, write a function to insert the value in a sorted way. Algorithm: Let input doubly linked list is sorted in increasing order. The new node passed to the function contains data in the data part and the previous and next links are set to NULL.

**2. Is doubly linked follows FIFO?**
In doubly or two-way linked lists, two pointers are used in the structure, where one pointer points in the forward direction and the other points in the backward direction. These two pointers allow us to traverse a linked list in both ways, that is, in First in First Out (FIFO) order as well as LIFO order.

**3. How do you sort a doubly linked list in C++?**
We can sort a doubly linked list as:
– Define a node current that will point to the head.
– Define another node index that will point to the node next to the current.
– Compare data of current and index nodes.
– Current will point to current.
– Continue this process till the entire list is sorted.