Reorder List

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.

Class Node:
    data (int)
    next (Node)

Input Format

First Parameter - Node head

Output Format

Return the Node

Example 1 :

Input :
    LinkedList : 1 2 3
Output : 
    1 3 2

Example 2 :

Input:
    LinkedList : 1 7 3 4
Output : 
    1 4 7 3

Constraints:

• The number of nodes in the list is in the range [1, 5 * 10⁴].
• 1 <= Node.data <= 1000
• Expected Time Complexity: O(N)
• Expected Auxiliary Space: O(1)