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

链表重排，这种题一定要画图，画着画着思路就出来了
边界条件：如果链表为空，或链表只有一个结点，或只有两个结点，直接返回head；
设置双指针，p指向奇数结点，q指向偶数结点，同时设置一个evenhead结点指向q，作为偶数链的头结点
1）让奇数结点指向偶数结点的下一个结点，同时p指针后移；
2）让偶数结点指向奇数结点的下一个结点，同时q指针后移；
3）以上两步做循环，直到奇数结点的下一个结点或偶数结点的下一个结点不存在，则退出

这里循环到最后有两种情况：
1.是原链表有奇数个结点，此时，p指向最后一个结点，q指向空结点
2.是原链表有偶数个结点，此时，p指向倒数第二个结点，q指向最后一个结点
这两种情况，p都指向奇数链表的最后一个结点，而偶数链表的尾结点的next都为nullptr
所以这两种情况可以直接合并处理，直接令奇数链表的尾结点指向偶数链表的头结点即可

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    ListNode* oddEvenList(ListNode* head) {
        // write code here
        // 链表的奇偶重排
        if(!head || !head->next || !head->next->next) return head;

        ListNode *p = head, *q = head->next, *evenhead = q;
        while (p->next && q->next) {
            p->next = q->next;
            p = p->next;
            q->next = p->next;
            q = q->next;
        }

        p->next = evenhead;
        return head;
    }
};