Linked List Partitioning

You are given a singly linked list node and an integer k. Order the linked list so that all nodes whose values are less than k come first, all nodes whose values are equal to k next, and then other nodes last.

The relative ordering of the nodes should remain the same.

Bonus: Can you do it in \(\mathcal{O}(n)$` time and `$\mathcal{O}(1)\) space?

Constraints

• n ≤ 100,000 where n is the number of nodes in node

https://binarysearch.com/problems/Linked-List-Partitioning

Examples

Example 1

Input

• node =

• k = 2

Output

• answer =

Solution