Reorder List

Reorder List

You are given the head of a singly linked list. The list can be represented as:

Reorder it to:

You may not modify the values in the list's nodes. Only nodes themselves may be changed.

Examples

Example 1:

Input: head = [1, 2, 3, 4]
Output: [1, 4, 2, 3]

Example 2:

Input: head = [1, 2, 3, 4, 5]
Output: [1, 5, 2, 4, 3]

Constraints

• The number of nodes in the list is in the range [1, 5 * 10^4].
• 1 <= Node.val <= 1000

Expected Complexity

• Time: O(n)
• Space: O(1)