Given a doubly-linked list containing N nodes, where each node is at most K away from its target position in the list, the task is to sort the given doubly linked list.
Examples:
Input: DLL: 3<->6<->2<->12<->56<->8, K = 2
Output:
2<->3<->6<->8<->12<->56Input: DLL: 3<->2<->1<->5<->4
Output:
1<->2<->3<->4<->5
Note: Approaches using Insertion sort and using Min Heap Data structure have been discussed here.
Approach: Shell sort, which is a variation of Insertion sort can be used to solve this problem as well, by initializing the gap with K instead of N, as the list is already K-sorted.
Below is an implementation of the above approach:
C++
#include <bits/stdc++.h>using namespace std;// A class to represent a node in a doubly linked listclass Node { public: int data; // data of the node Node* next; // pointer to the next node Node* prev; // pointer to the previous node // constructor to initialize the node Node(int d) { data = d; next = prev = nullptr; }};// function to print the doubly linked listvoid printList(Node* node){ while (node != nullptr) { cout << node->data << " "; node = node->next; }}// function to return the ceiling value of gap/2int nextGap(double gap){ if (gap < 2) return 0; return (int)std::ceil(gap / 2);}// function to sort a k sorted doubly linked listNode* sortAKSortedDLL(Node* head, int k){ if (head == nullptr || head->next == nullptr) return head; // for all gaps for (int gap = k; gap > 0; gap = nextGap(gap)) { Node *i = head, *j = head; int count = gap; // move j pointer k nodes ahead while (count-- > 0) j = j->next; // i and j pointers compare and swap for (; j != nullptr; i = i->next, j = j->next) { if (i->data > j->data) { // if i is head, then replace head with j if (i == head) head = j; // swap i & j pointers Node* iTemp = i; i = j; j = iTemp; // i & j pointers are swapped because // below code only swaps nodes by // swapping their associated // pointers(i.e. prev & next pointers) // Now, swap both the // nodes in linked list Node *iPrev = i->prev, *iNext = i->next; if (iPrev != nullptr) iPrev->next = j; if (iNext != nullptr) iNext->prev = j; i->prev = j->prev; i->next = j->next; if (j->prev != nullptr) j->prev->next = i; if (j->next != nullptr) j->next->prev = i; j->prev = iPrev; j->next = iNext; } } } return head;}void push(Node** head_ref, int new_data){ Node* new_node = new Node(new_data); new_node->prev = nullptr; new_node->next = *head_ref; if (*head_ref != nullptr) { (*head_ref)->prev = new_node; } *head_ref = new_node;}//Driver codeint main(){ Node* head = nullptr; 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:" << std::endl; printList(head); Node* sortedDLL = sortAKSortedDLL(head, k); cout << endl; cout << "Sorted Doubly linked list:" << std::endl; printList(sortedDLL); return 0;}// This code is contributed by lokeshpotta20. |
Java
// Java implementation to sort a k sorted doublyimport java.util.*;class DoublyLinkedList { static Node head; static class Node { int data; Node next, prev; Node(int d) { data = d; next = prev = null; } } // this method returns // the ceiling value of gap/2 int nextGap(double gap) { if (gap < 2) return 0; return (int)Math.ceil(gap / 2); } // Sort a k sorted Doubly Linked List // Time Complexity: O(n*log k) // Space Complexity: O(1) Node sortAKSortedDLL(Node head, int k) { if (head == null || head.next == null) return head; // for all gaps for (int gap = k; gap > 0; gap = nextGap(gap)) { Node i = head, j = head; int count = gap; while (count-- > 0) j = j.next; for (; j != null; i = i.next, j = j.next) { // if data at jth node is less than // data at ith node if (i.data > j.data) { // if i is head // then replace head with j if (i == head) head = j; // swap i & j pointers Node iTemp = i; i = j; j = iTemp; // i & j pointers are swapped because // below code only swaps nodes by // swapping their associated // pointers(i.e. prev & next pointers) // Now, swap both the // nodes in linked list Node iPrev = i.prev, iNext = i.next; if (iPrev != null) iPrev.next = j; if (iNext != null) iNext.prev = j; i.prev = j.prev; i.next = j.next; if (j.prev != null) j.prev.next = i; if (j.next != null) j.next.prev = i; j.prev = iPrev; j.next = iNext; } } } 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(); // 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); }} |
Python3
# Python implementation to sort a k sorted doubly linked listclass Node: def __init__(self, data): self.data = data self.next = None self.prev = Noneclass DoublyLinkedList: def __init__(self): self.head = None # this method returns the ceiling value of gap/2 def next_gap(self, gap): if gap < 2: return 0 return int(gap / 2 + 0.5) # Sort a k sorted Doubly Linked List # Time Complexity: O(n*log k) # Space Complexity: O(1) def sort_k_sorted_dll(self, head, k): if not head or not head.next: return head # for all gaps for gap in range(k, 0, -1): i = head j = head count = gap while count > 0 and j: j = j.next count -= 1 while j: # if data at jth node is less than data at ith node if i.data > j.data: # if i is head then replace head with j if i == head: head = j # swap i & j pointers i_temp = i i = j j = i_temp # Now, swap both the nodes in linked list i_prev = i.prev i_next = i.next if i_prev: i_prev.next = j if i_next: i_next.prev = j i.prev = j.prev i.next = j.next if j.prev: j.prev.next = i if j.next: j.next.prev = i j.prev = i_prev j.next = i_next i = i.next j = j.next return head # Function to insert a node # at the beginning of the # Doubly Linked List def push(self, new_data): # allocate node new_node = Node(new_data) # since we are adding at the beginning, # prev is always None new_node.prev = None # link the old list of the new node new_node.next = self.head # change prev of head node to new node if self.head: self.head.prev = new_node # move the head to point # to the new node self.head = new_node # Function to print nodes # in a given doubly linked list def print_list(self, node): while node: print(node.data, end=" ") node = node.nextif __name__ == "__main__": dll = DoublyLinkedList() # 3<->6<->2<->12<->56<->8 dll.push(8) dll.push(56) dll.push(12) dll.push(2) dll.push(6) dll.push(3) # setting k value k = 2 # print("Original Doubly linked list:") dll.print_list(dll.head) # sorting the linked list sorted_dll = dll.sort_k_sorted_dll(dll.head, k) print("\nDoubly Linked List after sorting:") dll.print_list(sorted_dll) |
C#
// C# implementation to sort a k sorted doublyusing System;public class DoublyList { public static Node head; public class Node { public int data; public Node next, prev; public Node(int d) { data = d; next = prev = null; } } // this method returns // the ceiling value of gap/2 int nextGap(double gap) { if (gap < 2) return 0; return (int)Math.Ceiling(gap / 2); } // Sort a k sorted Doubly Linked List // Time Complexity: O(n*log k) // Space Complexity: O(1) Node sortAKSortedDLL(Node head, int k) { if (head == null || head.next == null) return head; // for all gaps for (int gap = k; gap > 0; gap = nextGap(gap)) { Node i = head, j = head; int count = gap; while (count-- > 0) j = j.next; for (; j != null; i = i.next, j = j.next) { // if data at jth node is less than // data at ith node if (i.data > j.data) { // if i is head // then replace head with j if (i == head) head = j; // swap i & j pointers Node iTemp = i; i = j; j = iTemp; // i & j pointers are swapped because // below code only swaps nodes by // swapping their associated // pointers(i.e. prev & next pointers) // Now, swap both the // nodes in linked list Node iPrev = i.prev, iNext = i.next; if (iPrev != null) iPrev.next = j; if (iNext != null) iNext.prev = j; i.prev = j.prev; i.next = j.next; if (j.prev != null) j.prev.next = i; if (j.next != null) j.next.prev = i; j.prev = iPrev; j.next = iNext; } } } 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) { Console.Write(node.data + " "); node = node.next; } } // Driver code public static void Main(String[] args) { DoublyList list = new DoublyList(); // 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 umadevi9616 |
Javascript
<script>// javascript implementation to sort a k sorted doublyvar head; class Node { constructor(val) { this.data = val; this.prev = null; this.next = null; } } // this method returns // the ceiling value of gap/2 function nextGap(gap) { if (gap < 2) return 0; return parseInt( Math.ceil(gap / 2)); } // Sort a k sorted Doubly Linked List // Time Complexity: O(n*log k) // Space Complexity: O(1) function sortAKSortedDLL(head , k) { if (head == null || head.next == null) return head; // for all gaps for (var gap = k; gap > 0; gap = nextGap(gap)) { var i = head, j = head; var count = gap; while (count-- > 0) j = j.next; for (; j != null; i = i.next, j = j.next) { // if data at jth node is less than // data at ith node if (i.data > j.data) { // if i is head // then replace head with j if (i == head) head = j; // swap i & j pointers var iTemp = i; i = j; j = iTemp; // i & j pointers are swapped because // below code only swaps nodes by // swapping their associated // pointers(i.e. prev & next pointers) // Now, swap both the // nodes in linked list var iPrev = i.prev, iNext = i.next; if (iPrev != null) iPrev.next = j; if (iNext != null) iNext.prev = j; i.prev = j.prev; i.next = j.next; if (j.prev != null) j.prev.next = i; if (j.next != null) j.next.prev = i; j.prev = iPrev; j.next = iNext; } } } return head; } /* UTILITY FUNCTIONS */ // Function to insert a node // at the beginning of the // Doubly Linked List function push(new_data) { // allocate nodevar 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 // 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("<br/>"); document.write("Doubly Linked List after sorting:<br/>"); printList(sortedDLL);// This code contributed by umadevi9616 </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*log K)
gap is initialized with k and reduced to the ceiling value of gap/2 after each iteration. Hence, log k gaps will be calculated, and for each gap, the list will be iterated.
Space Complexity: 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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
