405. Rearrange Linked List for In-Place Quicksort (Partition)

Given a linked list, perform a single Lomuto partition step for in-place quicksort using the last node as the pivot: rearrange the nodes so that all values less than the pivot come first, then the pivot, then the values greater than or equal to the pivot, following the standard Lomuto partition order. Return the partitioned list as an array.

Input: An array of node values.

Output: Array — the list after one Lomuto partition.

Examples

Input: [3,7,8,5,2,1,9,5,4]
Output: [3,2,1,4,7,8,9,5,5]
Explanation: Partition around pivot 4 (last element).

Input: [2,1]
Output: [1,2]
Explanation: Pivot 1 moves to front.

Input: [1]
Output: [1]
Explanation: Single node.

Constraints

• 0<=n<=10^5
• -10^9<=value<=10^9

Asked by