![\"\"](\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645012425288-Article_211.png\")
<\/p>\n<\/p>\n
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.
\nIn 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.<\/p>\n
In this problem, we will be given K<\/strong> sorted doubly linked lists. We need to merge all lists such that the newly created doubly linked list is also in sorted order.<\/p>\n If you want to see how to merge K<\/strong> sorted singly-linked lists, check out these articles merge K sorted linked lists(set 1)<\/a> and merge K sorted linked lists(set 2 – using Min heap)<\/a>.<\/p>\n The problem statement is quite straightforward, we will be given K<\/strong> 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. <\/p>\n Let’s try to understand the problem with the help of an example: At this point, we have understood the problem statement. Now we will try to formulate an approach for this problem.<\/p>\n Before moving to the approach section, try to think about how you can approach this problem.<\/p>\n Let\u2019s move to the approach section.<\/p>\n To see how to merge two sorted linked lists, check out this article<\/a>.<\/p>\n Some Important Observations<\/strong><\/p>\n Time Complexity:<\/strong> O(n* K2<\/sup> ), n<\/strong> is the number of nodes in the list, and K<\/strong> is the total number of lists<\/p>\n Space Complexity:<\/strong> O(1)<\/p>\n 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.<\/p>\n ## Algorithm of how to sort k sorted doubly linked list<\/p>\n 1. Initialize a variable back<\/strong> with the last index of the array containing the head of all the lists. ## Code Implementation of how to sort k sorted doubly linked list<\/p>\n\t\t\t\t\t\t
\nIf the sorted doubly-linked lists given to us are:
\n![\"\"](\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/10\/p_1-10.jpg\")
<\/p>\n\n
\n![\"\"](\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/10\/p_2-10.jpg\")
<\/li>\n<\/ul>\n\n
Approach 1 of how to sort k sorted doubly linked list <\/h2>\n
\n
\n
\n
Approach 2 of how to sort k sorted doubly linked list <\/h2>\n
\n
\n
\n2. Run a while loop till back<\/strong> is not equal to zero.
\n – Inside while loop, we need to merge pairs so, initialize two variables, i.e., i<\/strong> with 0 and j<\/strong> with back<\/strong>.
\n – Now, we need to run a while loop as long as i<\/strong> is less than j<\/strong>.
\n – Now merge ith<\/sup> and jth<\/sup> list and store it as an ith<\/sup> element of the array.
\n – Now, increment i<\/strong> by one and decrement j<\/strong> by one.
\n – If i<\/strong> is greater than or equal to j<\/strong>, we need to update back<\/strong> by j<\/strong>.
\n3. After execution of both the while loops, we need to return the first element of the array.
\n4. In case you are not aware of how to merge two sorted linked lists, please check this article<\/a>.<\/p>\nDry Run of how to sort k sorted doubly linked list<\/h3>\n
![\"\"](\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/10\/p_3-8.jpg\")
\n![\"\"](\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/10\/p_4-6.jpg\")
<\/p>\n