# 重排链表
给定一个单链表 L 的头节点 head ，单链表 L 表示为：
L0 → L1 → … → Ln-1 → Ln
请将其重新排列后变为：
L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …
不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例 1:
输入: head = [1,2,3,4]
输出: [1,4,2,3]
示例 2:
输入: head = [1,2,3,4,5]
输出: [1,5,2,4,3]
提示：
- 链表的长度范围为
[1, 5 * 104]
1 <= node.val <= 1000
## template
```cpp
#include
using namespace std;
struct ListNode
{
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution
{
public:
void reorderList(ListNode *head)
{
ListNode *l1 = head, *l2 = head;
ListNode *tep = head;
int len = 0;
while (tep)
{
len++;
tep = tep->next;
}
if (len <= 2)
return;
int len1 = len / 2 + len % 2;
int len2 = len / 2;
for (int i = 0; i < len1 - 1; i++)
{
head = head->next;
}
l2 = head->next;
head->next = nullptr;
head = l1;
stack stk;
while (l2)
{
stk.push(l2);
l2 = l2->next;
}
while (!stk.empty())
{
tep = stk.top();
stk.pop();
tep->next = l1->next;
l1->next = tep;
l1 = tep->next;
}
}
};
```
## 答案
```cpp
```
## 选项
### A
```cpp
```
### B
```cpp
```
### C
```cpp
```