# Sort a K sorted Doubly Linked List | Set 2 (Using Shell Sort)

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:**

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.

Input:DLL: 3<->6<->2<->12<->56<->8, K = 2Output:

2<->3<->6<->8<->12<->56

Input:DLL: 3<->2<->1<->5<->4Output:

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:

## 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` `;` ` ` `}` ` ` `}` ` ` ` ` `// 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 off 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);` ` ` `}` `}` |

**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)