Partition Linked List

You are given the head of a singly linked list and an integer X. Your task is to partition the linked list around the value X such that:

All nodes with values less than X come first.

All nodes with values equal to X come next.

All nodes with values greater than X come at the end.

Crucially, the original relative order of the nodes within each of these three partitions must be preserved.

Your function should rearrange the nodes in-place (or by creating new lists and linking them) and return the head of the newly formed partitioned list.

Input Format:

The first line contains the node data for the linked list, separated by single spaces. The input is terminated by -1.

The second line contains a single integer X, the partition value.

Output Format:

Print a single line containing the data of the nodes in the partitioned linked list, separated by spaces.

Note:

The most straightforward and stable approach is to create three separate temporary linked lists: one for "less than X", one for "equal to X", and one for "greater than X". Iterate through the original list once, appending each node to the appropriate temporary list. Finally, connect the three temporary lists together to form the final result.