Given the head of a singly linked list, split it into two halves and return them as a list [first, second] of two heads. When the number of nodes is odd, the first half gets the extra node. The halves must be genuinely separated: the last node of the first half must point to None.
Examples
Input: head = 1 -> 2 -> 3 -> 4
Output: [1 -> 2, 3 -> 4]
Input: head = 1 -> 2 -> 3
Output: [1 -> 2, 3]
Input: head = (empty)
Output: [(empty), (empty)]
Constraints
0 <= number of nodes <= 10**4- Target: O(n) time, O(1) extra space, one pass (no counting pass first)
Goals
- Find the middle with a slow and a fast pointer
- Cut a list by setting a next pointer to None