LinkedListProblem 23 of 36Important
Sort a k sorted Doubly Linked list [Very IMP]
Sort a K-Sorted Doubly Linked List (Very Important)
Problem Statement
Given a doubly linked list containing n nodes, where each node is at most k positions away from its target position in the sorted list, sort the given doubly linked list. A k-sorted list means each element is at most k positions away from its sorted position.
Example
Input: 3 <-> 6 <-> 2 <-> 12 <-> 56 <-> 8, k = 2
Output: 2 <-> 3 <-> 6 <-> 8 <-> 12 <-> 56
Input: 2 <-> 1 <-> 3 <-> 5 <-> 4 <-> 6, k = 1
Output: 1 <-> 2 <-> 3 <-> 4 <-> 5 <-> 6
Brute Force Approach
Intuition
The brute force approach is to extract all values from the linked list, sort them using a standard sorting algorithm, and then rebuild the linked list with sorted values. This ignores the k-sorted property.
Algorithm
- Traverse the list and store all values in an array
- Sort the array using built-in sort function
- Traverse the list again and replace values with sorted values
- Return the head
Code
java
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
class Node {
int data;
Node prev;
Node next;
Node(int data) {
this.data = data;
this.prev = null;
this.next = null;
}
}
public class KSortedDLL {
public static Node sortKSortedBruteForce(Node head, int k) {
if (head == null || head.next == null) {
return head;
}
// Extract all values
List<Integer> values = new ArrayList<>();
Node temp = head;
while (temp != null) {
values.add(temp.data);
temp = temp.next;
}
// Sort the values
Collections.sort(values);
// Replace values in the list
temp = head;
int i = 0;
while (temp != null) {
temp.data = values.get(i++);
temp = temp.next;
}
return head;
}
public static void printList(Node head) {
while (head != null) {
System.out.print(head.data);
if (head.next != null) System.out.print(" <-> ");
head = head.next;
}
System.out.println();
}
}Complexity Analysis
- Time Complexity: O(n log n) - Due to the sorting step
- Space Complexity: O(n) - To store all values in an array
Optimal Approach
Intuition
Since each element is at most k positions away from its target position, we can use a min-heap (priority queue) of size k+1. The minimum element in the first k+1 elements will definitely be the first element of the sorted list. We maintain a sliding window of k+1 elements in the heap.
Algorithm
- Create a min-heap and insert first k+1 nodes
- Create a new sorted list by extracting minimum from heap
- For each remaining node, insert it into heap and extract minimum to add to result
- Empty the remaining heap to complete the sorted list
- Fix all prev pointers in the final list
Code
java
import java.util.PriorityQueue;
class Node {
int data;
Node prev;
Node next;
Node(int data) {
this.data = data;
this.prev = null;
this.next = null;
}
}
public class KSortedDLLOptimal {
public static Node sortKSortedOptimal(Node head, int k) {
if (head == null || head.next == null) {
return head;
}
// Min heap to store k+1 nodes
PriorityQueue<Node> minHeap = new PriorityQueue<>((a, b) -> a.data - b.data);
// Insert first k+1 nodes into the heap
Node curr = head;
for (int i = 0; i <= k && curr != null; i++) {
minHeap.offer(curr);
curr = curr.next;
}
Node newHead = null;
Node tail = null;
// Process remaining nodes
while (!minHeap.isEmpty()) {
// Extract minimum
Node minNode = minHeap.poll();
// Add to result list
if (newHead == null) {
newHead = minNode;
tail = minNode;
minNode.prev = null;
} else {
tail.next = minNode;
minNode.prev = tail;
tail = minNode;
}
// Add next node to heap
if (curr != null) {
minHeap.offer(curr);
curr = curr.next;
}
}
// Set the next of last node to null
if (tail != null) {
tail.next = null;
}
return newHead;
}
public static void printList(Node head) {
while (head != null) {
System.out.print(head.data);
if (head.next != null) System.out.print(" <-> ");
head = head.next;
}
System.out.println();
}
public static void main(String[] args) {
// Create sample list: 3 <-> 6 <-> 2 <-> 12 <-> 56 <-> 8
Node head = new Node(3);
Node curr = head;
int[] values = {6, 2, 12, 56, 8};
for (int val : values) {
Node newNode = new Node(val);
curr.next = newNode;
newNode.prev = curr;
curr = newNode;
}
int k = 2;
System.out.print("Original list: ");
printList(head);
head = sortKSortedOptimal(head, k);
System.out.print("Sorted list: ");
printList(head);
}
}Complexity Analysis
- Time Complexity: O(n log k) - Each element is inserted and extracted from a heap of size k+1
- Space Complexity: O(k) - The heap stores at most k+1 elements
Key Takeaways
- K-Sorted Property: Each element is at most k positions away from its correct position - this is a powerful constraint
- Min-Heap Window: Maintaining a heap of k+1 elements ensures the minimum is always the next element in sorted order
- Sliding Window with Heap: As we extract minimum, we add the next element maintaining the window
- Time Complexity Improvement: From O(n log n) to O(n log k) - significant when k << n
- Space Efficiency: Only O(k) space needed compared to O(n) in brute force
- DLL Reconstruction: Remember to properly update both prev and next pointers when reconstructing the sorted list
- Real-world Application: This pattern is useful when data arrives in nearly sorted order (like timestamps with small delays)