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

方法一：双指针

1、设置两个指针，奇数指针和偶数指针；

2、将奇数指针的下一结点为偶数指针的下一个结点；奇数指针移动到下一个结点后，此时将偶数指针的下一个结点设置为奇数指针的下一个结点，移动偶数指针。

时间复杂度：o(n)

空间复杂度：o(1)，不需要辅助空间

class Solution {
  public:
    ListNode* oddEvenList(ListNode* head) {
	  	//特殊情况处理
        if (head == nullptr || head->next == nullptr)
            return head;

        ListNode* odd = head;
        ListNode* even = head->next;
        ListNode* temp = even;

        while (even != nullptr && even->next != nullptr) {
            odd->next = even->next;
            odd = odd->next;
            even->next = odd->next;
            even = even->next;
        }
        odd->next = temp;

        return head;
    }
};

odd->next = temp不可写为odd->next = head->next，因为到这一步head->next已经不再是初始链表的结点了。

方法二：利用辅助空间

生成两个链表，一个保存奇数结点，另一个保存偶数结点，遍历完初始链表后，将奇数链表末尾连接至偶数链表头结点即可、

时间复杂度：o(n)

空间复杂度：o(n)

class Solution {
  public:
    ListNode* oddEvenList(ListNode* head) {
        if (head == nullptr || head->next == nullptr)
            return head;
		//生成两个链表，分别保存奇数结点和偶数结点
        ListNode* phead1 = new ListNode(0);
        ListNode* head1 = phead1;
        ListNode* phead2 = new ListNode(0);
        ListNode* head2 = phead2;

        while (head) {
            head1->next = new ListNode(head->val);
            head1 = head1->next;
            head = head->next;
            if (head) {
                head2->next = new ListNode(head->val);
                head2 = head2->next;
                head = head->next;
            }
        }
	  	//偶数链表末尾指向nullptr
        head2->next = nullptr;
	  	//奇数链表末尾指向偶数链表头结点
        head1->next  = phead2->next;

        return phead1->next;
    }
};