题解 | #链表的奇偶重排#

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * }j;
 */

#include <utility>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    ListNode* oddEvenList(ListNode* head) {
        if(not head) return head;
        
        std::vector<ListNode*> vec;
        for(auto cur = head; cur; cur = cur->next){
            vec.emplace_back(cur);
        }

        // 这里我们还是开一块儿空间做拷贝为佳
        decltype(vec) odds;
        decltype(vec) events;

        for(size_t idx = 0; idx < vec.size(); ++ idx) {
            if(idx & 1) odds.emplace_back(vec[idx]);
            else events.emplace_back(vec[idx]);
        }
        // 再将结果拼接回去
        auto mid = std::move(events.begin(), events.end(), vec.begin());
        std::move( odds.begin(), odds.end(), mid);
        
        for(auto it = vec.begin(); it != vec.end(); ++ it) {
            if(it + 1 != vec.end()) {
                (*it)->next = (*(it+1));
            }
        }
        vec.back()->next = {};

        return vec.front();
    }
};