题目描述

给定一个单链表，请将所有偶数节点拎出来，放在奇数节点后面。注意，偶数节点指位置编号是偶数的节点，并非指值是偶数的节点，奇数节点同理。

你需要使用 $O(n)$ 时间和额外 $O(1)$ 空间的算法。

注意：

• 奇数节点和偶数节点的相对顺序不能改变；
• 节点编号从1开始，即第一个点是奇数节点；

样例1

输入：1->2->3->4->5->NULL
输出：1->3->5->2->4->NULL

样例2

输入：2->1->3->5->6->4->7->NULL
输出：2->3->6->7->1->5->4->NULL

算法

(链表) $O(n)$

从前往后遍历整个链表，遍历时维护四个指针：奇数链表头结点，奇数链表尾节点，偶数链表头结点，偶数链表尾节点。

遍历时将位置编号是奇数的节点插在奇数链表尾节点后面，将位置编号是偶数的节点插在偶数链表尾节点后面。

遍历完整个链表后，将偶数链表头结点插在奇数链表尾节点后面即可。

时间复杂度分析：整个链表只遍历一次，所以时间复杂度是 $O(n)$，遍历时只记录了常数个额外的指针，所以额外的空间复杂度是 $O(1)$。

C++ 代码

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