reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…
You must do this in-place without altering the nodes' values.
For example,
Given {1,2,3,4}, reorder it to {1,4,2,3}.
前面用了O(1)空间的解法，但是我觉得不是那么好理解，然后向用O(n)空间，看看能不能加速一下运行速度。但是结果运行速度都是一样的。看来还是前面一种方法好点，不过这种方法的优点就是我觉得比较好理解。
解法：
1. 用vector存储Link
2. 用另外一个vector存储插入适当顺序的Link
3. 重新链接好各个->next，得到最终需要的Link结果
LeetCode
论坛上的程序也是我贴的，链接：leetCode
程序如下：
class Solution {
public:
void reorderList(ListNode *head)
{
if(head==nullptr || head->next==nullptr ||head->next==nullptr) return;
vector vln;
changeToVector(head, vln);
vector
vlnOut;
reodVector(vlnOut, vln);
chainVec(vlnOut);
}
void changeToVector(ListNode *head, vector& vln)
{
ListNode *ph = head;
while (ph!=nullptr)
{
vln.push_back(ph);
ph = ph->next;
}
}
void reodVector(vector& vlnOut, vector& vlnIn)
{
int n = vlnIn.size();
int r = (n-1)/2;
int i = 0;
int k = n-1;
for (; k>=(n-r); i++, k--)
{
vlnOut.push_back(vlnIn[i]);
vlnOut.push_back(vlnIn[k]);
}
while(i& vln)
{
int n = vln.size();
for (int i = 0; i < n-1; i++)
{
vln[i]->next = vln[i+1];
}
vln[n-1]->next = nullptr;
}
};