Reorder List
Reorder List
Given an array of integers. Create a Linked List from these numbers.
Write a method ReorderList
that reorders a list L0
→ L1
→ L2
→ ... → Ln-1
→ Ln
into L0
→ Ln
→ L1
→ Ln-1
→ L2
→ Ln-2
→ ... .
Write the code according to the next interface:
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
};
You can create (use) additional methods if needed.
Input
The first line contains number n (1 ≤ n ≤ 10000). The second line contains n integers.
Output
Print the elements of reordered Linked List using Print method.
5 1 2 3 4 5
1 5 2 4 3