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