Sort a k sorted doubly linked list

Read

Discuss

Given a doubly linked list containing n nodes, where each node is at most k away from its target position in the list. The problem is to sort the given doubly linked list.
For example, let us consider k is 2, a node at position 7 in the sorted doubly linked list, can be at positions 5, 6, 7, 8, 9 in the given doubly linked list.

Examples:

Naive Approach: Sort the given doubly linked list using the insertion sort technique. While inserting each element in the sorted part of the list, there will be at most k swaps to place the element to its correct position since it is at most k steps away from its correct position.

C++

// C++ implementation to sort a k sorted doubly
// linked list
#include<bits/stdc++.h>
using namespace std;
 
// a node of the doubly linked list
struct Node {
    int data;
    struct Node* next;
    struct Node* prev;
};
 
 
// function to sort a k sorted doubly linked list
struct Node* sortAKSortedDLL(struct Node* head, int k)
{
    if(head == NULL || head->next == NULL)
        return head;
  
    // perform on all the nodes in list
    for(Node *i = head->next; i != NULL; i = i->next) {
        Node *j = i;
          // There will be atmost k swaps for each element in the list
        // since each node is k steps away from its correct position
        while(j->prev != NULL && j->data < j->prev->data) {
              // swap j and j.prev node
            Node* temp = j->prev->prev;
            Node* temp2 = j->prev;
            Node *temp3 = j->next;
            j->prev->next = temp3;
            j->prev->prev = j;
            j->prev = temp;
            j->next = temp2;
            if(temp != NULL)
                temp->next = j;
            if(temp3 != NULL)
                temp3->prev = temp2;
        }
          // if j is now the new head
       // then reset head
        if(j->prev == NULL)
            head = j;
    }
    return head;
}
 
// Function to insert a node at the beginning
// of the Doubly Linked List
void push(struct Node** head_ref, int new_data)
{
    // allocate node
    struct Node* new_node =
        (struct Node*)malloc(sizeof(struct Node));
 
    // put in the data
    new_node->data = new_data;
 
    // since we are adding at the beginning,
    // prev is always NULL
    new_node->prev = NULL;
 
    // link the old list of the new node
    new_node->next = (*head_ref);
 
    // change prev of head node to new node
    if ((*head_ref) != NULL)
        (*head_ref)->prev = new_node;
 
    // move the head to point to the new node
    (*head_ref) = new_node;
}
 
// Function to print nodes in a given doubly linked list
void printList(struct Node* head)
{
    // if list is empty
    if (head == NULL)
        cout << "Doubly Linked list empty";
 
    while (head != NULL) {
        cout << head->data << " ";
        head = head->next;
    }
}
 
// Driver program to test above
int main()
{
    struct Node* head = NULL;
 
    // Create the doubly linked list:
    // 3<->6<->2<->12<->56<->8
    push(&head, 8);
    push(&head, 56);
    push(&head, 12);
    push(&head, 2);
    push(&head, 6);
    push(&head, 3);
 
    int k = 2;
 
    cout << "Original Doubly linked list:\n";
    printList(head);
 
    // sort the biotonic DLL
    head = sortAKSortedDLL(head, k);
 
    cout << "\nDoubly Linked List after sorting:\n";
    printList(head);
 
    return 0;
}
 
// This code is contributed by sachinejain74754.

Java

// Java implementation to sort a k sorted doubly
import java.util.*;
class DoublyLinkedList
{
static Node head;
static class Node
{
    int data;
    Node next, prev;
    Node(int d)
    {
    data = d;
    next = prev = null;
    }
}
 
// function to sort a k sorted doubly linked list
// Using Insertion Sort
// Time Complexity: O(n*k)
// Space Complexity: O(1)
Node sortAKSortedDLL( Node head, int k) {
      if(head == null || head.next == null) 
        return head;
 
    // perform on all the nodes in list
    for(Node i = head.next; i != null; i = i.next) {
        Node j = i;
          // There will be atmost k swaps for each element in the list
        // since each node is k steps away from its correct position
        while(j.prev != null && j.data < j.prev.data) {
              // swap j and j.prev node
            Node temp = j.prev.prev;
            Node temp2 = j.prev;
            Node temp3 = j.next;
            j.prev.next = temp3;
            j.prev.prev = j;
            j.prev = temp;
            j.next = temp2;
            if(temp != null)
                temp.next = j;
            if(temp3 != null)
                temp3.prev = temp2;
        }
          // if j is now the new head
       // then reset head
        if(j.prev == null)
            head = j;
    }
    return head;
}
 
/* UTILITY FUNCTIONS */
/* Function to insert a node at the beginning of the
    * Doubly Linked List */
void push(int new_data)
{
    /* allocate node */
    Node new_node = new Node(new_data);
 
    /* since we are adding at the beginning,
        prev is always NULL */
    new_node.prev = null;
 
    /* link the old list of the new node */
    new_node.next = head;
 
    /* change prev of head node to new node */
    if (head != null)
    {
    head.prev = new_node;
    }
 
    /* move the head to point to the new node */
    head = new_node;
}
 
/* Function to print nodes in a given doubly linked list
    This function is same as printList() of singly linked
    list */
void printList(Node node)
{
    while (node != null)
    {
    System.out.print(node.data + " ");
    node = node.next;
    }
}
 
// Driver code
public static void main(String[] args)
{
    DoublyLinkedList list = new DoublyLinkedList();
 
    /* Let us create a k sorted doubly linked list to test the
        functions Created doubly linked list will be 3<->6<->2<->12<->56<->8
    */
    list.push(8);
    list.push(56);
    list.push(12);
    list.push(2);
    list.push(6);
    list.push(3);
 
    int k = 2;
 
    System.out.println("Original Doubly linked list:");
    list.printList(head);
 
    Node sortedDLL = list.sortAKSortedDLL(head, k);
    System.out.println("");
    System.out.println("Doubly Linked List after sorting:");
    list.printList(sortedDLL);
}
}
 
// This code is contributed by Mittul Mandhan(@mittulmandhan)

Python3

# Python implementation to sort a k sorted doublyclass DoublyLinkedList {
head = None
 
class Node:
    def __init__(self, val):
        self.data = val
        self.prev = None
        self.next = None
 
# function to sort a k sorted doubly linked list
# Using Insertion Sort
# Time Complexity: O(n*k)
# Space Complexity: O(1)
def sortAKSortedDLL(head , k):
    if (head == None or head.next == None):
        return head
 
    # perform on all the nodes in list
    i = head.next
    while(i != None):
        j = i
         
        # There will be atmost k swaps for each element in the list
        # since each node is k steps away from its correct position
        while (j.prev != None and j.data < j.prev.data):
           
            # swap j and j.prev node
            temp = j.prev.prev
            temp2 = j.prev
            temp3 = j.next
            j.prev.next = temp3
            j.prev.prev = j
            j.prev = temp
            j.next = temp2
            if (temp != None):
                temp.next = j
            if (temp3 != None):
                temp3.prev = temp2
                 
            # if j is now the new head
            # then reset head
        if (j.prev == None):
            head = j
        i = i.next
 
    return head
 
# UTILITY FUNCTIONS 
#
# Function to insert a node at the beginning of the Doubly Linked List
def push(new_data):
 
    global head
     
    # allocate node
    new_node = Node(new_data)
 
    #
    # since we are adding at the beginning, prev is always NULL
    #
    new_node.prev = None
 
    # link the old list of the new node 
    new_node.next = head
 
    # change prev of head node to new node
    if (head != None):
        head.prev = new_node
 
    # move the head to point to the new node
    head = new_node
 
# Function to print nodes in a given doubly linked list This function is same
# as printList() of singly linked list
def printList(node):
    while (node != None):
        print(node.data,end = " ")
        node = node.next
 
# Driver code
 
# Let us create a k sorted doubly linked list to test the functions Created
# doubly linked list will be 3<->6<->2<->12<->56<->8
push(8)
push(56)
push(12)
push(2)
push(6)
push(3)
 
k = 2
 
print("Original Doubly linked list:")
printList(head)
 
sortedDLL = sortAKSortedDLL(head, k)
print("")
print("Doubly Linked List after sorting:")
printList(sortedDLL)
 
# This codeis contributed by shinjanpatra

C#

// C# implementation to sort a k sorted doubly lists
using System;
 
class DoublyLinkedList {
  static Node head;
 
  public class Node {
    public int data;
    public Node next, prev;
    public Node(int d)
    {
      data = d;
      next = prev = null;
    }
  }
 
  // function to sort a k sorted doubly linked list
  // Using Insertion Sort
  // Time Complexity: O(n*k)
  // Space Complexity: O(1)
  public Node sortAKSortedDLL(Node head, int k)
  {
    if (head == null || head.next == null)
      return head;
 
    // perform on all the nodes in list
    for (Node i = head.next; i != null; i = i.next) {
      Node j = i;
 
      // There will be atmost k swaps for each element
      // in the list since each node is k steps away
      // from its correct position
      while (j.prev != null && j.data < j.prev.data)
      {
 
        // swap j and j.prev node
        Node temp = j.prev.prev;
        Node temp2 = j.prev;
        Node temp3 = j.next;
        j.prev.next = temp3;
        j.prev.prev = j;
        j.prev = temp;
        j.next = temp2;
        if (temp != null)
          temp.next = j;
        if (temp3 != null)
          temp3.prev = temp2;
      }
 
      // if j is now the new head
      // then reset head
      if (j.prev == null)
        head = j;
    }
    return head;
  }
 
  /* UTILITY FUNCTIONS */
  /* Function to insert a node at the beginning of the
     * Doubly Linked List */
  public void push(int new_data)
  {
 
    /* allocate node */
    Node new_node = new Node(new_data);
 
    /* since we are adding at the beginning,
        prev is always NULL */
    new_node.prev = null;
 
    /* link the old list of the new node */
    new_node.next = head;
 
    /* change prev of head node to new node */
    if (head != null) {
      head.prev = new_node;
    }
 
    /* move the head to point to the new node */
    head = new_node;
  }
 
  /* Function to print nodes in a given doubly linked list
    This function is same as printList() of singly linked
    list */
  public void printList(Node node)
  {
    while (node != null) {
      Console.Write(node.data + " ");
      node = node.next;
    }
  }
 
  // Driver Code
  public static void Main(string[] args)
  {
    DoublyLinkedList list = new DoublyLinkedList();
 
    /* Let us create a k sorted doubly linked list to
           test the functions Created doubly linked list
           will be 3<->6<->2<->12<->56<->8
        */
    list.push(8);
    list.push(56);
    list.push(12);
    list.push(2);
    list.push(6);
    list.push(3);
 
    int k = 2;
 
    Console.WriteLine("Original Doubly linked list:");
    list.printList(head);
 
    Node sortedDLL = list.sortAKSortedDLL(head, k);
    Console.WriteLine();
 
    Console.WriteLine(
      "Doubly Linked List after sorting:");
    list.printList(sortedDLL);
  }
}
 
// This code is contributed by Tapesh (tapeshdua420)

Javascript

<script>
// javascript implementation to sort a k sorted doublyclass DoublyLinkedList {
    var head;
 
     class Node {
            constructor(val) {
                this.data = val;
                this.prev = null;
                this.next = null;
            }
        }
 
    // function to sort a k sorted doubly linked list
    // Using Insertion Sort
    // Time Complexity: O(n*k)
    // Space Complexity: O(1)
    function sortAKSortedDLL(head , k) {
        if (head == null || head.next == null)
            return head;
 
        // perform on all the nodes in list
        for (i = head.next; i != null; i = i.next) {
    var j = i;
            // There will be atmost k swaps for each element in the list
            // since each node is k steps away from its correct position
            while (j.prev != null && j.data < j.prev.data) {
                // swap j and j.prev node
        var temp = j.prev.prev;
        var temp2 = j.prev;
        var temp3 = j.next;
                j.prev.next = temp3;
                j.prev.prev = j;
                j.prev = temp;
                j.next = temp2;
                if (temp != null)
                    temp.next = j;
                if (temp3 != null)
                    temp3.prev = temp2;
            }
            // if j is now the new head
            // then reset head
            if (j.prev == null)
                head = j;
        }
        return head;
    }
 
    /* UTILITY FUNCTIONS */
    /*
     * Function to insert a node at the beginning of the Doubly Linked List
     */
    function push(new_data) {
        /* allocate node */
var new_node = new Node(new_data);
 
        /*
         * since we are adding at the beginning, prev is always NULL
         */
        new_node.prev = null;
 
        /* link the old list of the new node */
        new_node.next = head;
 
        /* change prev of head node to new node */
        if (head != null) {
            head.prev = new_node;
        }
 
        /* move the head to point to the new node */
        head = new_node;
    }
 
    /*
     * Function to print nodes in a given doubly linked list This function is same
     * as printList() of singly linked list
     */
    function printList(node) {
        while (node != null) {
            document.write(node.data + " ");
            node = node.next;
        }
    }
 
    // Driver code
     
            /*
         * Let us create a k sorted doubly linked list to test the functions Created
         * doubly linked list will be 3<->6<->2<->12<->56<->8
         */
        push(8);
        push(56);
        push(12);
        push(2);
        push(6);
        push(3);
 
        var k = 2;
 
        document.write("Original Doubly linked list:<br/>");
        printList(head);
 
var sortedDLL = sortAKSortedDLL(head, k);
        document.write("");
        document.write("<br/>Doubly Linked List after sorting:<br/>");
        printList(sortedDLL);
 
// This code contributed by aashish1995
</script>

Output

Original Doubly linked list:
3 6 2 12 56 8 
Doubly Linked List after sorting:
2 3 6 8 12 56

Time Complexity: O(n*k)
Auxiliary Space: O(1)

Efficient Approach: We can sort the list using the MIN HEAP data structure. The approach has been explained in Sort a nearly sorted (or K sorted) array. We only have to be careful while traversing the input doubly linked list and adjusting the required next and previous links in the final sorted list.

Implementation:

CPP

// C++ implementation to sort a k sorted doubly
// linked list
#include <bits/stdc++.h>
using namespace std;
 
// a node of the doubly linked list
struct Node {
    int data;
    struct Node* next;
    struct Node* prev;
};
 
// 'compare' function used to build up the
// priority queue
struct compare {
    bool operator()(struct Node* p1, struct Node* p2)
    {
        return p1->data > p2->data;
    }
};
 
// function to sort a k sorted doubly linked list
struct Node* sortAKSortedDLL(struct Node* head, int k)
{
    // if list is empty
    if (head == NULL)
        return head;
 
    // priority_queue 'pq' implemented as min heap with the
    // help of 'compare' function
    priority_queue<Node*, vector<Node*>, compare> pq;
 
    struct Node* newHead = NULL, *last;
 
    // Create a Min Heap of first (k+1) elements from
    // input doubly linked list
    for (int i = 0; head != NULL && i <= k; i++) {
        // push the node on to 'pq'
        pq.push(head);
 
        // move to the next node
        head = head->next;
    }
 
    // loop till there are elements in 'pq'
    while (!pq.empty()) {
 
        // place root or top of 'pq' at the end of the
        // result sorted list so far having the first node
        // pointed to by 'newHead'
        // and adjust the required links
        if (newHead == NULL) {
            newHead = pq.top();
            newHead->prev = NULL;
 
            // 'last' points to the last node
            // of the result sorted list so far
            last = newHead;
        }
 
        else {
            last->next = pq.top();
            pq.top()->prev = last;
            last = pq.top();
        }
 
        // remove element from 'pq'
        pq.pop();
 
        // if there are more nodes left in the input list
        if (head != NULL) {
            // push the node on to 'pq'
            pq.push(head);
 
            // move to the next node
            head = head->next;
        }
    }
 
    // making 'next' of last node point to NULL
    last->next = NULL;
 
    // new head of the required sorted DLL
    return newHead;
}
 
// Function to insert a node at the beginning
// of the Doubly Linked List
void push(struct Node** head_ref, int new_data)
{
    // allocate node
    struct Node* new_node = 
          (struct Node*)malloc(sizeof(struct Node));
 
    // put in the data
    new_node->data = new_data;
 
    // since we are adding at the beginning,
    // prev is always NULL
    new_node->prev = NULL;
 
    // link the old list of the new node
    new_node->next = (*head_ref);
 
    // change prev of head node to new node
    if ((*head_ref) != NULL)
        (*head_ref)->prev = new_node;
 
    // move the head to point to the new node
    (*head_ref) = new_node;
}
 
// Function to print nodes in a given doubly linked list
void printList(struct Node* head)
{
    // if list is empty
    if (head == NULL)
        cout << "Doubly Linked list empty";
 
    while (head != NULL) {
        cout << head->data << " ";
        head = head->next;
    }
}
 
// Driver program to test above
int main()
{
    struct Node* head = NULL;
 
    // Create the doubly linked list:
    // 3<->6<->2<->12<->56<->8
    push(&head, 8);
    push(&head, 56);
    push(&head, 12);
    push(&head, 2);
    push(&head, 6);
    push(&head, 3);
 
    int k = 2;
 
    cout << "Original Doubly linked list:\n";
    printList(head);
 
    // sort the biotonic DLL
    head = sortAKSortedDLL(head, k);
 
    cout << "\nDoubly Linked List after sorting:\n";
    printList(head);
 
    return 0;
}

Java

// Java implementation to sort a k sorted doubly 
import java.util.*;
class DoublyLinkedList
{
  static Node head;
  static class Node 
  {
    int data;
    Node next, prev;
    Node(int d)
    {
      data = d;
      next = prev = null;
    }
  }
  class compareNode implements Comparator<Node>
  {
    public int compare(Node n1, Node n2){
      return n1.data-n2.data;
    }
  }
 
  // function to sort a k sorted doubly linked list 
  Node sortAKSortedDLL( Node head, int k) 
  { 
     
    // if list is empty 
    if (head == null) 
      return head; 
 
    // priority_queue 'pq' implemented as min heap with the 
    // help of 'compare' function in compare Node class
    PriorityQueue<Node> pq = new PriorityQueue<Node>(new compareNode()); 
 
    Node newHead = null, last = null; 
 
    // Create a Min Heap of first (k+1) elements from 
    // input doubly linked list 
    for (int i = 0; head != null && i <= k; i++) 
    {
       
      // push the node on to 'pq' 
      pq.add(head); 
 
      // move to the next node 
      head = head.next; 
    } 
 
    // loop till there are elements in 'pq' 
    while (!pq.isEmpty())
    { 
 
      // place root or top of 'pq' at the end of the 
      // result sorted list so far having the first node 
      // pointed to by 'newHead' 
      // and adjust the required links 
      if (newHead == null) 
      { 
        newHead = pq.peek(); 
        newHead.prev = null; 
 
        // 'last' points to the last node 
        // of the result sorted list so far 
        last = newHead; 
      } 
 
      else
      { 
        last.next = pq.peek(); 
        pq.peek().prev = last; 
        last = pq.peek(); 
      } 
 
      // remove element from 'pq' 
      pq.poll(); 
 
      // if there are more nodes left in the input list 
      if (head != null) 
      {
         
        // push the node on to 'pq' 
        pq.add(head); 
 
        // move to the next node 
        head = head.next; 
      } 
    } 
 
    // making 'next' of last node point to NULL 
    last.next = null; 
 
    // new head of the required sorted DLL 
    return newHead; 
  } 
 
  /* UTILITY FUNCTIONS */
  /* Function to insert a node at the beginning of the
     * Doubly Linked List */
  void push(int new_data)
  {
    /* allocate node */
    Node new_node = new Node(new_data);
 
    /* since we are adding at the beginning,
         prev is always NULL */
    new_node.prev = null;
 
    /* link the old list of the new node */
    new_node.next = head;
 
    /* change prev of head node to new node */
    if (head != null) 
    {
      head.prev = new_node;
    }
 
    /* move the head to point to the new node */
    head = new_node;
  }
 
  /* Function to print nodes in a given doubly linked list
     This function is same as printList() of singly linked
     list */
  void printList(Node node)
  {
    while (node != null)
    {
      System.out.print(node.data + " ");
      node = node.next;
    }
  }
 
  // Driver code
  public static void main(String[] args)
  {
    DoublyLinkedList list = new DoublyLinkedList();
 
    /* Let us create a k sorted doubly linked list to test the
         functions Created doubly linked list will be 3<->6<->2<->12<->56<->8 
       */
    list.push(8);
    list.push(56);
    list.push(12);
    list.push(2);
    list.push(6);
    list.push(3);
 
    int k = 2;
 
    System.out.println("Original Doubly linked list:");
    list.printList(head);
 
    Node sortedDLL = list.sortAKSortedDLL(head, k);
    System.out.println("");
    System.out.println("Doubly Linked List after sorting:");
    list.printList(sortedDLL);
  }
}
 
// This code is contributed by Kushagra Keserwani

Python3

# Python implementation to sort a k sorted doubly linked list
import heapq
head = None
 
#  a node of the doubly linked list
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
        self.prev = None
 
# function to sort a k sorted doubly linked list
def sortAKSortedDLL(head, k):
    # if list is empty
    if head == None:
        return head
 
    pq = []
 
    newHead = None
    last = None
 
    for i in range(k+1):
        # push the node
        heapq.heappush(pq, (head.data, head))
        # move to the next node
        head = head.next
 
    # loop till there are elements in 'pq'
    while len(pq) > 0:
 
        if newHead == None:
            newHead = heapq.heappop(pq)[1]
            newHead.prev = None
 
        #  'last' points to the last node of the result sorted list so far
            last = newHead
        else:
            last.next = heapq.heappop(pq)[1]
            last.next.prev = last
            last = last.next
 
        # if there are more nodes left in the input list
        if head != None:
            # push the node
            heapq.heappush(pq, (head.data, head))
 
            # move to the next node
            head = head.next
 
    # making 'next' of last node point to NULL
    last.next = None
 
    # new head of the required sorted DLL
    return newHead
 
# Function to insert a node at the beginning of the Doubly Linked List
def push(new_data):
 
    global head
 
    # allocate node
    new_node = Node(new_data)
 
    # since we are adding at the beginning, prev is always NULL
    new_node.prev = None
 
    # link the old list of the new node
    new_node.next = head
 
    # change prev of head node to new node
    if (head != None):
        head.prev = new_node
 
    # move the head to point to the new node
    head = new_node
 
 
# Function to print nodes in a given doubly linked list
def printList(head):
    # if list is empty
    if head is None:
        print("Doubly Linked list empty")
 
    while head is not None:
        print(head.data, end=" ")
        head = head.next
 
 
# Driver code
if __name__ == '__main__':
 
    # Create the doubly linked list:
    # 3<->6<->2<->12<->56<->8
    push(8)
    push(56)
    push(12)
    push(2)
    push(6)
    push(3)
 
    k = 2
 
    print("Original Doubly linked list:")
    printList(head)
 
    sortedDLL = sortAKSortedDLL(head, k)
 
    print("\nDoubly Linked List after sorting:")
    printList(sortedDLL)
 
# This code is contributed by Tapesh(tapeshdua420)

C#

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
 
// C# implementation to sort a k sorted doubly 
class Node 
{
  public int data;
  public Node next, prev;
  public Node(int d)
  {
    data = d;
    next = prev = null;
  }
}
 
class DoublyLinkedList
{
 
  public   Node head;
  // function to sort a k sorted doubly linked list 
  public  Node sortAKSortedDLL(Node head, int k) 
  { 
 
    // if list is empty 
    if (head == null) 
      return head; 
 
    // priority_queue 'pq' implemented as min heap with the 
    // help of 'compare' function in compare Node class
    List<Node> pq = new List<Node>();
 
    Node newHead = null, last = null; 
 
    // Create a Min Heap of first (k+1) elements from 
    // input doubly linked list 
    for (int i = 0; head != null && i <= k; i++) 
    {
 
      // push the node on to 'pq' 
      pq.Add(head); 
      pq.Sort(delegate(Node x, Node y){
        return x.data.CompareTo(y.data);
      });
      // move to the next node 
      head = head.next; 
    } 
 
    // loop till there are elements in 'pq' 
    while (pq.Count > 0)
    { 
 
      // place root or top of 'pq' at the end of the 
      // result sorted list so far having the first node 
      // pointed to by 'newHead' 
      // and adjust the required links 
      if (newHead == null) 
      { 
        newHead = pq[0]; 
        newHead.prev = null; 
 
        // 'last' points to the last node 
        // of the result sorted list so far 
        last = newHead; 
      } 
 
      else
      { 
        last.next = pq[0]; 
        pq[0].prev = last; 
        last = pq[0]; 
      } 
 
      // remove element from 'pq' 
      pq.RemoveAt(0); 
 
      // if there are more nodes left in the input list 
      if (head != null) 
      {
 
        // push the node on to 'pq' 
        pq.Add(head); 
        pq.Sort(delegate(Node x, Node y){
          return x.data.CompareTo(y.data);
        });
        // move to the next node 
        head = head.next; 
      } 
    } 
 
    // making 'next' of last node point to NULL 
    last.next = null; 
 
    // new head of the required sorted DLL 
    return newHead; 
  } 
 
  /* UTILITY FUNCTIONS */
  /* Function to insert a node at the beginning of the
     * Doubly Linked List */
  public  Node push(int new_data)
  {
    /* allocate node */
    Node new_node = new Node(new_data);
 
    /* since we are adding at the beginning,
         prev is always NULL */
    new_node.prev = null;
 
    /* link the old list of the new node */
    new_node.next = head;
 
    /* change prev of head node to new node */
    if (head != null) 
    {
      head.prev = new_node;
    }
 
    /* move the head to point to the new node */
    head = new_node;
 
    return head;
  }
 
  /* Function to print nodes in a given doubly linked list
     This function is same as printList() of singly linked
     list */
  public void printList(Node node)
  {
    while (node != null)
    {
      Console.Write(node.data + " ");
      node = node.next;
    }
  }
 
}
 
// This code is contributed by Kushagra Keserwani
 
class HelloWorld {
 
  static void Main() {
    DoublyLinkedList list = new DoublyLinkedList();
 
    /* Let us create a k sorted doubly linked list to test the
             functions Created doubly linked list will be 3<->6<->2<->12<->56<->8 
           */
    Node head = list.push(8);
    head = list.push(56);
    head = list.push(12);
    head = list.push(2);
    head = list.push(6);
    head = list.push(3);
 
    int k = 2;
 
    Console.WriteLine("Original Doubly linked list:");
    list.printList(head);
 
    Node sortedDLL = list.sortAKSortedDLL(head, k);
    Console.WriteLine("");
    Console.WriteLine("Doubly Linked List after sorting:");
    list.printList(sortedDLL);
  }
}
 
// The code is contributed by Nidhi goel.

Javascript

// javascript implementation to sort a k sorted doubly
// linked list
 
// a node of the doubly linked list
class Node {
     
    constructor(val){
        this.data = val;
        this.next = null;
        this.prev = null;
    }
}
 
 
// function to sort a k sorted doubly linked list
function sortAKSortedDLL(head, k)
{
    // if list is empty
    if (head == null)
        return head;
 
    // priority_queue 'pq' implemented as min heap with the
    // help of 'compare' function
    let pq = [];
 
    let newHead = null;
    let last = null;
 
    // Create a Min Heap of first (k+1) elements from
    // input doubly linked list
    for (let i = 0; head != null && i <= k; i++) {
        // push the node on to 'pq'
        pq.push(head);
        pq.sort(function(a, b){
            return a.data - b.data;
        });
        // move to the next node
        head = head.next;
    }
 
    // loop till there are elements in 'pq'
    while (pq.length > 0) {
 
        // place root or top of 'pq' at the end of the
        // result sorted list so far having the first node
        // pointed to by 'newHead'
        // and adjust the required links
        if (newHead == null) {
            newHead = pq[0];
            newHead.prev = null;
 
            // 'last' points to the last node
            // of the result sorted list so far
            last = newHead;
        }
 
        else {
            last.next = pq[0];
            pq[0].prev = last;
            last = pq[0];
        }
 
        // remove element from 'pq'
        pq.shift();
 
        // if there are more nodes left in the input list
        if (head != null) {
            // push the node on to 'pq'
            pq.push(head);
            pq.sort(function (a, b){
                return a.data - b.data;
            });
 
            // move to the next node
            head = head.next;
        }
    }
 
    // making 'next' of last node point to NULL
    last.next = null;
 
    // new head of the required sorted DLL
    return newHead;
}
 
// Function to insert a node at the beginning
// of the Doubly Linked List
function push(head, new_data)
{
    // allocate node
    let new_node = new Node(new_data);
 
    // put in the data
    new_node.data = new_data;
 
    // since we are adding at the beginning,
    // prev is always NULL
    new_node.prev = null;
 
    // link the old list of the new node
    new_node.next = head;
 
    // change prev of head node to new node
    if (head != null)
        head.prev = new_node;
 
    // move the head to point to the new node
    head = new_node;
     
    return head;
}
 
// Function to print nodes in a given doubly linked list
function printList(head)
{
    // if list is empty
    if (head == null)
        console.log("Doubly Linked list empty\n");
     
    let temp = "";
    while (head != null) {
        temp = temp + head.data + " ";
        // console.log(head.data + " ");
        head = head.next;
    }
    console.log(temp);
}
 
// Driver program to test above
let head = null;
 
// Create the doubly linked list:
// 3<->6<->2<->12<->56<->8
head = push(head, 8);
head = push(head, 56);
head = push(head, 12);
head = push(head, 2);
head = push(head, 6);
head = push(head, 3);
 
let k = 2;
 
console.log("Original Doubly linked list:");
printList(head);
 
// sort the biotonic DLL
head = sortAKSortedDLL(head, k);
 
console.log("\nDoubly Linked List after sorting:");
printList(head);
 
 
// the code is contributed by Nidhi goel.

Output

Original Doubly linked list:
3 6 2 12 56 8 
Doubly linked list after sorting:
2 3 6 8 12 56

Time Complexity: O(n*log k)
Auxiliary Space: O(k)

If you like GeeksforGeeks and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks.

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

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 geeks!

Last Updated : 14 Mar, 2023

Sort a k sorted doubly linked list

C++

Java

Python3

C#

Javascript

CPP

Java

Python3

C#

Javascript

Please Login to comment...