Reorder List
Medium · Linked Lists · Linked List · Two Pointers · Stack · Recursion
Problem
You are given the head of a singly linked list L0 → L1 → … → Ln-1 → Ln. Rearrange it in place into
L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …
taking nodes alternately from the front and from the back until they meet in the middle.
Move the nodes themselves: changing the values stored in them is not allowed. The method returns nothing — the tests read the list from the head they passed in, with to_list(), after your method returns. The list can hold 50,000 nodes, so an approach that walks to the end of the list once per node is too slow, and so is recursion that goes one call deeper per node.
Examples
Input: head = 1 -> 2 -> 3 -> 4 Output: 1 -> 4 -> 2 -> 3
First 1 from the front, then 4 from the back, then 2 from the front and 3 from the back.
Input: head = 1 -> 2 -> 3 -> 4 -> 5 Output: 1 -> 5 -> 2 -> 4 -> 3
With an odd number of nodes, the middle one, 3, ends up last.
Constraints
- 1 <= number of nodes <= 5 * 10^4
- 1 <= Node.val <= 1000
Approaches
- Move the last node forward, over and over — time O(n²), space O(1)
Related problems
Start free on Cariara · Coding problems · System design studio
