Given the head node of a singly linked list and an integer threshold, rearrange the list so that all nodes with values less than the threshold appear before nodes with values greater than or equal to the threshold. The relative order of nodes in each partition must be preserved. Return the head node of the modified list.
Example 1
Input: head = ListNode(7, ListNode(3, ListNode(9, ListNode(1)))) threshold = 5
Output: [3,1,7,9]
Explanation: Nodes with values less than 5 are [3,1], followed by nodes >= 5 [7,9].
Example 2
Input: head = ListNode(0, ListNode(-1, ListNode(2, ListNode(5)))) threshold = 2
Output: [0,-1,2,5]
Explanation: Nodes less than 2 are [0,-1], followed by nodes >= 2 [2,5].
Example 3
Input: head = None threshold = 10
Output: []
Explanation: Empty list remains empty.
Constraints
Case 1
Input: head = ListNode(8, ListNode(6, ListNode(4, ListNode(2)))) threshold = 5
Expected: [4,2,8,6]
Case 2
Input: head = ListNode(5, ListNode(5, ListNode(5))) threshold = 5
Expected: [5,5,5]
Case 3
Input: head = ListNode(-10, ListNode(0, ListNode(10))) threshold = 0
Expected: [-10,0,10]
Case 4
Input: head = ListNode(1) threshold = 0
Expected: [1]
Case 5
Input: head = ListNode(2, ListNode(1, ListNode(3, ListNode(4)))) threshold = 3
Expected: [2,1,3,4]