42. Reorder List

Medium · Linked List

Given a singly linked list, reorder it such that nodes at even indices are followed by nodes at odd indices in reverse order. Specifically, the pattern becomes: 1st node, last node, 2nd node, 2nd-to-last node, and so on.

For example, a list [1, 2, 3, 4, 5] should be reordered to [1, 5, 2, 4, 3].

Modify the list in-place and return the head of the reordered list.

Examples

Example 1
Input: [1, 2, 3, 4]
Output: [1, 4, 2, 3]
Explanation: The list is reordered by taking alternately from the start and end: 1 (1st), 4 (last), 2 (2nd), 3 (2nd-to-last).
Example 2
Input: [1, 2, 3, 4, 5]
Output: [1, 5, 2, 4, 3]
Explanation: Alternating from start and end: 1 (1st), 5 (last), 2 (2nd), 4 (2nd-to-last), 3 (middle).

Constraints