You get the head of a singly linked list with nodes in this order:
L0 -> L1 -> L2 -> ... -> Ln-2 -> Ln-1 -> Ln
Rearrange it into:
L0 -> Ln -> L1 -> Ln-1 -> L2 -> Ln-2 -> ...
In words, take nodes from the two ends in turn. Take one from the front, then one from the back. Keep moving inward until every node is placed once.
Only the next links may change. Keep every value in its node, and don't make new nodes.
The function returns nothing. It rearranges the list in place. The list still starts at head, and the tests print it from there.
Example 1:
Input: head = [10,20,30,40,50,60] Output: [10,60,20,50,30,40] Explanation: The two ends come first: 10, then 60. Next come 20 and 50. Last come 30 and 40, the middle pair.
Example 2:
Input: head = [2,9,4,7,5] Output: [2,5,9,7,4] Explanation: The two ends come first: 2, then 5. Next come 9 and 7. The list has an odd number of nodes. So the middle node, 4, is left over and comes last.
Example 3:
Input: head = [6] Output: [6] Explanation: A single node has nothing to move.
Constraints:
- 1 to 50,000 nodes.
- Each value is from 1 to 1,000.
- Values can repeat.
Note:
Your algorithm should run in O(n) time and use O(1) extra space, where n is the number of nodes: it only re-links the nodes that are already there. Copying the nodes into a vector first would take O(n) extra space.
It takes three passes over the list:
- Find the middle with two pointers. A slow one moves one node at a time, and a fast one moves two. Cut the list after the middle: 1->2->3->4->5 becomes 1->2->3 and 4->5.
- Reverse the second half, as in Reverse Linked List: 4->5 becomes 5->4.
- Take nodes from the two halves in turn: 1->5->2->4->3.
Free plan: 30 tutor messages. PRO is unlimited.
