All problems

Reorder List

Medium · linked list

You are given the head of a singly linked list. Rearrange its nodes so that the list reads: the first node, then the last node, then the second node, then the second-to-last node, and so on, taking turns between the two ends and moving inwards until every node has been used.

For a list a0 → a1 → a2 → ... → a(k-1) the result is a0 → a(k-1) → a1 → a(k-2) → a2 → .... When the two ends meet, the middle node (if there is one) simply comes last.

Return the head of the rearranged list. The head is always the same node you were given. The nodes you receive are ListNode objects with a val and a next, and the last node of the result must have a next pointing to no node.

Examples

Example 1

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

Output: [1, 4, 2, 3]

Take 1 (first), 4 (last), 2 (next from the front), 3 (next from the back).

Example 2

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

Output: [1, 5, 2, 4, 3]

After 1, 5, 2, 4 the two ends have met on 3, which closes the list.

Example 3

Input: head = [7]

Output: [7]

A single node is already in the required order.

Constraints