LeetCode Reorder List O(n) space空间解法

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<ListNode *> vln;  
        changeToVector(head, vln);  
        vector<ListNode *> vlnOut;  
        reodVector(vlnOut, vln);  
        chainVec(vlnOut);  
    }  
  
    void changeToVector(ListNode *head, vector<ListNode *>& vln)  
    {  
        ListNode *ph = head;  
        while (ph!=nullptr)  
        {  
            vln.push_back(ph);  
            ph = ph->next;  
        }  
    }  
  
    void reodVector(vector<ListNode *>& vlnOut, vector<ListNode *>& 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<n-r)  
        {  
            vlnOut.push_back(vlnIn[i]);  
            i++;  
        }  
    }  
  
    void chainVec(vector<ListNode *>& vln)  
    {  
        int n = vln.size();  
        for (int i = 0; i < n-1; i++)  
        {  
            vln[i]->next = vln[i+1];  
        }  
        vln[n-1]->next = nullptr;  
    }  
};  

 

 

补充：软件开发 , C++ ,