Standard Bar Linked List · Medium Problems of LL O(N log N) · O(log N)
A job scheduler's queue is a one-way chain whose entries landed in arbitrary priority order, and the dispatcher needs the whole chain ascending without exporting it to an array — memory is reserved for the chain itself. The viable strategy is merge sort: split the chain at the middle, sort each half the same way, then zip two already-sorted chains together.
Input: An array head of node values representing the linked list.
Output: The values of the list sorted in ascending order.
0 <= list length <= 10^5-10^9 <= node value <= 10^9Input: {"head":[4,2,1,3]}
Output: [1,2,3,4]
Four scrambled entries come out fully ascending after the split-sort-merge rounds.
Input: {"head":[-1,5,3,4,0]}
Output: [-1,0,3,4,5]
Negatives and zero rank below the positives in the merged chain.