Linked Lists Reversing and rewiring
299. Reorder List
You are given head, the first node of a singly linked list. Call its nodes L0, L1, …,
Ln−1 from the head on. Relink the nodes so that the list takes one node from the front, then one
from the back, and keeps going until every node is used:
L0 → Ln−1 → L1 → Ln−2 → L2 → Ln−3 → …
Change the list itself. The function returns nothing, and the list is read from the same head node after
your function finishes. Move the nodes by changing their next pointers. Do not change the value in any
node, and do not create new nodes.
The examples write a list as its values from the head on, so head = [4,1,6] is the list 4 → 1 → 6.
Example 1
Input: head = [3, 8, 1, 9, 4, 6, 2]
[3,2,8,6,1,4,9]Explanation: The order takes the first node (3), the last (2), the second (8), the second to last (6), the third (1) and the third to last (4). The middle node, 9, is left over and comes last.
Example 2
Input: head = [10, 20, 30, 40, 50, 60]
[10,60,20,50,30,40]Explanation: With six nodes the front and the back take turns three times each. The list ends on 40, the second of the two middle nodes.
Example 3
Input: head = [-7, 0]
[-7,0]Explanation: The first node is followed by the last node, which is already the order of a list of two. Nothing moves.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
1 ≤ number of nodes ≤ 105-109 ≤ Node.val ≤ 109
Clarifying questions
What you would ask an interviewer before writing any code.