Given the head of a linked list, head, reorder the list to alternate between nodes from the start and the end of the list. The reordering should be performed by rearranging the nodes themselves, without modifying the values stored in the nodes.

The original structure is as follows:

L0 → L1 → ... → Ln-1 → Ln

Reorganize the list into this structure:

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

The linked list is represented by a sequence of ListNodes, where each node points to the next node in the sequence, or null if it is the last node.

A ListNode has the following interface:

interface ListNode {
  val: number;
  next: ListNode | null;
}

Input

• head: ListNode: Head of the linked list. Examples display each linked list as an array of values within the list

Input: list = [9,9,10,7,10,6,4,2,3,1]
Output: [9,1,9,3,10,2,7,4,10,6]
Explanation: The list is reordered to alternate between the start and end of the list.

Input: list = [1,2,3,4,5,6]
Output: [1,6,2,5,3,4]
Explanation: The list is reordered to alternate between the start and end of the list.

Constraints

• 1 <= Number of nodes <= 1000
• 1 <= ListNode.val <= 1000