Reorder List

Given an array of integers, create a Linked List from these numbers.

Write a method ReorderList that reorders a list L_0 \rightarrow L_1 \rightarrow L_2 \rightarrow \ldots \rightarrow L_{n-1} \rightarrow L_n into L_0 \rightarrow L_n \rightarrow L_1 \rightarrow L_{n-1} \rightarrow L_2 \rightarrow L_{n-2} \rightarrow \ldots.

Write the code according to the following interface:

=== "C++" "'cpp class Node public: int data; Node *next; Node() : next(NULL) ; Node(int data, Node *next = NULL) : data(data), next(next) ; ;

class List public: Node *head, *tail; List() : head(NULL), tail(NULL) ; void addToTail(int val); // Add number val to the end of the Linked List void ReorderList(void); // Reorder a list as given above void Print(void); // Print the elements of Linked List ; "' === "Python" "'python class Node:

def __init__(self, data: int): self.data: int = data self.next: [Node | None] = None

class List:

def __init__(self): self.head: [Node | None] = None self.tail: [Node | None] = None

def addToTail(self, val: int) -> None: """Add number val to the end of the Linked List""" pass

def ReorderList(self) -> None: """Reorder a list as given above""" pass

def Print(self) -> None: """Print the elements of Linked List""" pass "'

You may create (use) additional methods if needed.