Sort a k sorted doubly linked list

Given a doubly linked list, each node is at most k-indices away from its target position. The problem is to sort the given doubly linked list. The distance can be assumed in either of the directions (left and right).

Examples :

Input: Doubly Linked List : 3 <-> 2 <-> 1 <-> 5 <-> 6 <-> 4 , k = 2
Output: 1 <-> 2 <-> 3 <-> 4 <-> 5 <-> 6

Explanation: After sorting the given 2-sorted list is 1 <-> 2 <-> 3 <-> 4 <-> 5 <-> 6.

Input: Doubly Linked List : 5 <-> 6 <-> 7 <-> 3 <-> 4 <-> 4 , k = 3
Output: 3 <-> 4 <-> 4 <-> 5 <-> 6 <-> 7

Explanation: After sorting the given 3-sorted list is 3 <-> 4 <-> 4 <-> 5 <-> 6 <-> 7.

Expected Time Complexity: O(n*logk)
Expected Auxiliary Space: O(k)
Constraints:
1 <= number of nodes <= 10⁵
1 <= k < number of nodes
1 <= node->data <= 10⁹

Approach 01:

class Solution {
public:
    // Function to sort a k-sorted doubly linked list
    DLLNode* sortAKSortedDLL(DLLNode* head, int k) {
        DLLNode* currentNode = head;
        priority_queue<int, vector<int>, greater<int>> minHeap;

        // Insert the first k elements into the priority queue
        while (currentNode && k--) {
            minHeap.push(currentNode->data);
            currentNode = currentNode->next;
        }

        DLLNode* sortedNode = head;
        while (sortedNode) {
            if (currentNode) {
                minHeap.push(currentNode->data);
                currentNode = currentNode->next;
            }

            // Assign the minimum element from the heap to the current node
            sortedNode->data = minHeap.top();
            minHeap.pop();
            sortedNode = sortedNode->next;
        }

        return head;
    }
};

import heapq

class Solution:
    def sortAKSortedDLL(self, head, k):
        currentNode = head
        minHeap = []
        
        while currentNode and k > 0:
            heapq.heappush(minHeap, currentNode.data)
            currentNode = currentNode.next
            k -= 1
        
        sortedNode = head
        while sortedNode:
            if currentNode:
                heapq.heappush(minHeap, currentNode.data)
                currentNode = currentNode.next
            
            sortedNode.data = heapq.heappop(minHeap)
            sortedNode = sortedNode.next
        
        return head

Time Complexity

• Inserting Elements into the Min-Heap:

  Initially, the first k elements are inserted into the heap. Inserting each element into the heap takes \(O(\log k)\) time. For the remaining elements, each insertion takes \(O(\log k)\) time, as the heap size is limited to \(k + 1\) elements.

• Processing Each Node:

  For each node in the list, we perform an insertion and deletion from the heap. Since the list contains \(n\) nodes, and heap operations take \(O(\log k)\), this gives us a time complexity of \(O(n \log k)\).

• Overall Time Complexity:

  The overall time complexity is \(O(n \log k)\), where \(n\) is the number of nodes in the doubly linked list and \(k\) is the number of adjacent nodes that are misplaced from their correct position.

Space Complexity

• Auxiliary Data Structures:

  The priority queue (min-heap) holds at most \(k + 1\) elements at any given time. Therefore, the space required for the heap is \(O(k)\).

• Overall Space Complexity:

  The overall space complexity is \(O(k)\) due to the auxiliary space used by the min-heap.