# Reorder List Problem

## Description

LeetCode Problem 143.

You are given the head of a singly linked-list. The list can be represented as:

``````1
L_0 -> L_1 -> ... -> L_n - 1 -> L_n
``````

Reorder the list to be on the following form:

``````1
L_0 -> L_n -> L_1 -> L_n - 1 -> L_2 -> L_n - 2 -> ...
``````

You may not modify the values in the list’s nodes. Only nodes themselves may be changed.

Example 1:

``````1
2
Output: [1,4,2,3]
``````

Example 2:

``````1
2
Output: [1,5,2,4,3]
``````

Constraints:

• The number of nodes in the list is in the range [1, 5 * 10^4].
• 1 <= Node.val <= 1000

## Sample C++ Code

``````1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
// Edge cases

stack<ListNode*> my_stack;
int size = 0;
while (ptr != NULL) {
// Put all nodes in stack
my_stack.push(ptr);
size++;
ptr = ptr->next;
}

for (int j=0; j<size/2; j++) {
// Between every two nodes insert the one in the top of the stack
ListNode *element = my_stack.top();
my_stack.pop();
element->next = pptr->next;
pptr->next = element;
pptr = pptr->next->next;
}
pptr->next = NULL;
}
};
``````