Given the head of a singly linked list head and an integer x, reorder the list so that all nodes with value strictly less than x appear before all nodes with value greater than or equal to x.

The relative order of nodes within each of the two groups must remain the same as in the original list.

Implement Optional[ListNode] partition(self, Optional[ListNode] head, int x) and return the head of the reordered list.

Constraints:

• The number of nodes in the list is in the range $[0, 200]$

• $-100 \leq$ Node.val $\leq 100$

• $-200 \leq$ x $\leq 200$

Now, let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.