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

方法一 辅助数组

• 用两个数组分别储存odd和even位上的值，再修改原链表上节点的val

class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        // write code here
        vector<int> odd;
        vector<int> even;
        ListNode* cur = head;
        int i = 1;
        while(cur){
            if(i % 2 == 0){
                even.push_back(cur->val);
            }else{
                odd.push_back(cur->val);
            }
            cur = cur->next;
            i++;
        }
        cur = head;
        for(int j = 0; j < odd.size(); j++){
            cur->val = odd[j];
            cur = cur->next;
        }
        for(int j = 0; j < even.size(); j++){
            cur->val = even[j];
            cur = cur->next;
        }
        return head;
    }
};

方法二 双指针

奇数节点后是偶数节点，偶数节点的头节点是第二个节点，维护两个指针，奇数节点的下一个节点指向相邻偶数节点的下一个节点

class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        // write code here
        if(!head) return head;
        ListNode* oddhead = head;
        ListNode* evenhead = head->next;
        ListNode* odd = oddhead;
        ListNode* even = evenhead;
        while(even && even->next){
            odd->next = even->next;
            odd = odd->next;
            even->next = odd->next;
            even = even->next;
        }
        odd->next = evenhead;
        return head;
    }
};