Reorder a singly linked list by alternating nodes from the start and the end.
You are given the head of a singly linked list. Reorder the list so that the nodes appear in the pattern:
L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → ...
where L0 is the first node, Ln is the last node, and so on.
The values stored in the nodes must not be changed. You should rearrange the node links in place as much as possible.
Input Format
- A singly linked list represented by its head node.
- Each node contains an integer value and a pointer to the next node.
Output Format
- Return the head of the reordered linked list, or modify the list in place depending on the platform API.
Constraints
- The list length is at least 0.
- The algorithm should use extra space if possible.
- Node values must not be modified; only links may be rearranged.
Example 1
Input
head = [1,2,3,4]
Output
[1,4,2,3]
Explanation
The list is reordered by taking one node from the front, then one from the back, alternating until all nodes are used.
Example 2
Input
head = [1,2,3,4,5]
Output
[1,5,2,4,3]
Explanation
After splitting around the middle, reverse the second half and merge the two halves alternately.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.