143 Reorder List

Given a singly linked list L: <i>L</i>: <i>L</i>₀→<i>L</i>₁→…→<i>L</i>_<i>n</i>-1→<i>L</i>_n,
reorder it to: <i>L</i>₀→<i>L</i>_<i>n</i>→<i>L</i>₁→<i>L</i>_<i>n</i>-1→<i>L</i>₂→<i>L</i>_<i>n</i>-2→…

You must do this in-place without altering the nodes' values.

For example,
Given <code>{1,2,3,4}</code>, reorder it to <code>{1,4,2,3}</code>.

解题思路

这本来是一道链表转换为另一个链表的题目。但是转换方式过于奇葩，实在不适合链表来做（链表更适合于做插入删除类的操做，或者是相邻元素之间的操作），于是果断决定先用个<code>vector</code>存起来，再进行转换。

代码

class Solution {
public:
    void reorderList(ListNode* head) {
        vector<int> res;
        ListNode* s = head;
        while (s != NULL){
            res.push_back(s->val); s = s->next;
        }
        int l = 0, r = res.size()-1;
        ListNode* t = head;
        while (l <= r){
            t->val = res[l++];
            t = t->next;
            if (t == NULL) break;
            t->val = res[r--];
            t = t->next;
            if (t == NULL) break;
        }
    }
};