Reorder List

Medium

Given the head of a singly linked list L0 → L1 → ... → Ln-1 → Ln, reorder it to L0 → Ln → L1 → Ln-1 → L2 → .... Return the reordered list. (LeetCode mutates in place and returns void; here return the head.)

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

• 1 <= number of nodes <= 5*10^4
• 0 <= Node.val <= 1000