Partition List Nodes Stably around a Threshold
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
### Problem
Partition the nodes of a singly linked list around `x`. Every node with value less than `x` must precede every node with value greater than or equal to `x`. Within each of these two groups, preserve the original relative node order.
Use the supplied `ListNode` type with `val` and `next` fields and return the resulting head:
```cpp
ListNode* partition(ListNode* head, int x);
```
### Examples
```text
Input: head = [5,1,4,2,3,0], x = 3
Output list: [1,2,0,5,4,3]
```
The smaller group keeps 1,2,0 in that order, and the other group keeps 5,4,3.
```text
Input: head = [2,-1,2], x = 2
Output list: [-1,2,2]
```
### Constraints
- There are between 0 and 200 nodes.
- Node values lie between -100 and 100, inclusive.
- `-200 <= x <= 200`.
- Stability is required independently in both groups; equal-to-`x` nodes belong to the second group.
Overview: Stably partition linked-list nodes around a threshold while preserving relative order within both groups.
