linked-list
two-pointers
in-place
Given the head of a singly linked list, group all nodes at odd positions together followed by all nodes at even positions, and return the reordered list. Positions are 1-indexed (the head is position 1, which is odd).
You should keep the relative order of the odd-positioned nodes and the relative order of the even-positioned nodes unchanged, and solve it in place in O(1) extra space (not counting the output).
Input / output
- Input:
head: ListNode - Output:
ListNode
Constraints
- 0 <= number of nodes <= 10,000
- -1,000,000 <= node value <= 1,000,000
Follow-up
Can you do it in a single pass, without counting the list's length first?
Examples
Example 1
Input: head = [1,2,3,4,5]
Output: [1,3,5,2,4]
Example 2
Input: head = [2,1,3,5,6,4,7]
Output: [2,3,6,7,1,5,4]
Example 3 (empty list)
Input: head = []
Output: []
🔒 6 hidden
Running will execute all 9 cases, including 6 hidden ones.