To implement the prominent sorting algorithm, Quicksort, the most vital step is partitioning the sequence by a value pivot. Specifically, given a sequence (linked list in this case) and a value pivot, you should partition the sequence such that all elements less than pivot come before the ones greater than or equal to pivot, and the orders within each part should be preserved.
For instance, if we have the sequence {1, 3, 8, 2, 8} and pivot=3, then the partitioned sequence would be {1, 2, 3, 8, 8}, where {1, 2} is the part less than pivot and {3, 8, 8} is the one greater than or equal to pivot.
Please note that this is a partial-judged problem. That is, you are required to define the function:
node *partition_linked_list(node *, int);
Where node is declared as:
typedef struct _node
{
int val;
struct _node *next;
} node;
The function would be called with the head of the linked list and the pivot.
It's guaranteed that the sum of the length of the linked lists would not exceed 100000.
It should return the head of the partitioned linked list.
Could you do it in-place, i.e., without using additional space?