328. 奇偶链表

328. 奇偶链表

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        if(!head || !head->next)
            return head;
        ListNode* odd = head;
        ListNode* even = head->next;
        ListNode* eh = even;
        ListNode* pt = even->next;
        while(pt)
        {
            odd->next = pt;
            odd = pt;
            pt = pt->next;
            if(!pt)
                break;
            even->next = pt;
            even = pt;
            pt = pt->next;
        }
        even->next = nullptr;
        odd->next = eh;
        return head;
    }
};

更好看一些

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        if(!head || !head->next)
            return head;
        ListNode* odd = head;
        ListNode* even = head->next;
        ListNode* eh = even;
        // 因为先处理的是even->next，所以只要even->next非空，odd在下面就不会是空
        // 当长度为奇数时候，在最后一个循环中，odd会走到最末尾的节点，然后even->next就是nullptr
        // 当长度为偶数时候，在最后一个循环中，odd走到倒数第二个节点，然后even走到最后一个节点，这样的话even->next本来就是nullptr
        // 这里顺序不能调换，因为even是在odd后面的节点
        while(even && even->next)
        {
            odd->next = even->next;
            odd = odd->next;
            even->next = odd->next;
            even = even->next;
        }
        odd->next = eh;
        return head;
    }
};