题目描述
给定一个单链表 L：L0→L1→…→Ln-1→Ln ，
将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
题解
利用双向队列，问题就很简单了。
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
| void reorderList(ListNode* head) {
if (!head || !head->next)return;
deque<ListNode*> de;
ListNode*tmp = head->next;
while (tmp)
{
de.push_back(tmp);
tmp = tmp->next;
}
tmp = head;
while (!de.empty())
{
tmp->next = de.back();
de.pop_back();
tmp = tmp->next;
if (de.empty())
tmp->next = NULL;
else
{
tmp->next = de.front();
de.pop_front();
tmp = tmp->next;
}
}
tmp->next = NULL;
}
|