Reorder List

Hard~25 min

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

L0 → L1 → … → Ln-1 → Ln

Reorder the list to be on the following form:

L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …

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

Note: This function modifies the list in-place and does not return anything.

Examples

Example 1
Input: head = [1, 2, 3, 4]
Output: [1, 4, 2, 3]
Explanation: Reordered: L0 → L3 → L1 → L2, which gives [1, 4, 2, 3].
Example 2
Input: head = [1, 2, 3, 4, 5]
Output: [1, 5, 2, 4, 3]
Explanation: Reordered: L0 → L4 → L1 → L3 → L2, which gives [1, 5, 2, 4, 3].
Example 3
Input: head = [1]
Output: [1]
Explanation: A single node list is already in the correct form.

Constraints

  • The number of nodes in the list is in the range [1, 5 * 10^4]
  • 1 <= Node.val <= 1000
  • Expected time complexity: O(n)
Code
Ctrl+EnterRun|Ctrl+⇧+EnterSubmit
Output

Run your code to see results

Use Cmd+Enter to run