题解 | #重排链表#

首先把链表中的所有结点都保存到vector中，然后双指针left和right分别向数组中间走，重新按照要求拉链。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void reorderList(ListNode *head) {
        vector<ListNode*> vec{};
        auto cur=head;
        while(cur){
            ListNode* temp=cur;
            cur=cur->next;
            temp->next=nullptr;
            vec.push_back(temp);
        }
        ListNode* dummy_head=new ListNode{-1};
        cur=dummy_head;
        for(int i=0,j=vec.size()-1;i<=j;i++,j--){
            cur->next=vec[i];
            cur=cur->next;
            if(i!=j){
                cur->next=vec[j];
                cur=cur->next;
            }
        }
        head=dummy_head->next;
    }
};