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

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    ListNode* oddEvenList(ListNode* head) {
        // write code here
        //思路：跳跃式的将链表分成两个链表，然后链接
        if(head == nullptr || head->next == nullptr) return head;

        ListNode oddhead(-1);
        ListNode evenhead(-1);

        ListNode* even = &evenhead;
        ListNode* odd = &oddhead;
        ListNode* p = head;
	  //将head转换成奇偶两个链表
        while(p != nullptr && p->next != nullptr)
        {
            ListNode* evennext = p->next;
            odd->next = p;
            odd = odd->next;
            odd->next = nullptr;
            p = evennext->next;

            even->next = evennext;
            even = even->next;
            even->next = nullptr;
        }
	  //while做完会出现两种情况，一是p==nullptr，那么我们什么都不要做，直接连接。
	  //如果p！=nullptr，那么还有一个元素结点，并且他一定是奇数，添加到odd的后面，移动odd
        if(p!= nullptr)
        {
            odd->next = p;
            odd = odd->next;
        }
	  //组合两个链表
        odd->next = evenhead.next;
        return oddhead.next;
    }
};