258. Sort a K-Sorted Doubly Linked List

A doubly linked list contains n values where each value is guaranteed to be at most k positions away from where it would sit in the fully sorted list. Sort the list and print the sorted values.

Input: The first line contains an integer n. The second line contains n space-separated integers, the doubly linked list's values, each at most k positions from its sorted position. The third line contains k. Output: Print the fully sorted values, space-separated, on one line.

1 <= n <= 10^5, 0 <= k < n

This is the linked-list version of the array-based 'Sort a Nearly Sorted (K-Sorted) Array' problem from the Heap category - the exact same size-(k+1) min-heap technique applies, just adapted to relink list nodes instead of writing into an array.

Sort a doubly linked list where every value is guaranteed to be at most k positions away from its correct sorted position. Brute force: Sort the whole list with a general O(n log n) algorithm, ignoring the k-sorted guarantee entirely - this works but is slower than necessary when k is much smaller than n. Optimised: Because no value is more than k positions from its correct sorted position, the TRUE minimum of the whole remaining list is GUARANTEED to already be among the first k+1 unprocessed values - a min-heap of size just k+1 is always enough to know the next output value correctly, giving O(n log k) instead of the general O(n log n).

Load the first k+1 node values into a min-heap. Then, walking through the rest of the list, repeatedly pop the current minimum (guaranteed to be the next smallest overall value, since nothing smaller can appear more than k nodes later) into the output, and push the next node's value into the heap. This keeps the same correctness guarantee as the insertion-sort approach but replaces its O(k) backward walk with an O(log k) heap operation per element, which is faster whenever k is large relative to how cheap heap operations are. Time: O(n log k) Space: O(k)

Extract every value from the doubly linked list into an array, sort that array with a generic comparison sort while ignoring the fact that no element is more than k positions from its sorted position, then write the sorted values back into the list nodes in order. This is correct for any input regardless of k, but it throws away the bounded-displacement guarantee that could otherwise be exploited for a faster or more memory-light solution. Time: O(n log n) Space: O(n)

Exploit the k-sorted guarantee directly on the doubly linked list itself: walk through the list and, for each node, use the existing prev pointers to walk it backward at most k steps until it reaches its correct sorted position, relinking pointers in place (much like insertion sort, but bounded by k instead of the full list length). This uses the list's own prev/next pointers as the only 'storage' needed, avoiding the array conversion of the brute-force approach entirely. Time: O(n*k) Space: O(1)

1. Insert the first k+1 values into a min-heap. 2. Repeatedly pop the minimum from the heap (that's guaranteed to be the next correctly-sorted output value) and push in the next unread value from the list, if any remain. 3. Continue until the whole list has been processed and the heap is empty.

Time: O(n log k) - each of the n values triggers one O(log k) heap operation. Space: O(k), for the size-(k+1) min-heap.

k = 0 (the list is already sorted); k = n-1 (the maximum allowed displacement); n = 10^5 for confirming the O(n log k) approach performs well.

Be ready to explain WHY a heap of exactly size k+1 (not k, and not some other size) is sufficient - this precise bound follows directly from the problem's own 'at most k positions away' guarantee.