← 返回 capitalone 的题目列表Reorder a Singly Linked List in L0→Ln→L1→Ln-1… Order
类型：online_judge
Given the head of a singly linked list head, reorder the list into the following order:
L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → ...
where Li is the i-th node in the original list and Ln is the last node.
Constraints / requirements:
You may not modify node values; you must change the next pointers.
Aim for O(1) extra space.
I/O convention (for the tests here)
Input: one line of space-separated integers representing the linked list values.
Output: one line of space-separated integers representing the reordered list values.
Scale
1 <= n <= 2 * 10^5
Values fit in 32-bit signed integer.
Examples
Input:
1 2 3 4
Output:
1 4 2 3
Input:
1 2 3 4 5
Output:
1 5 2 4 3
Example
Input
1 2 3 4
Output
1 4 2 3