将单链表奇数移到偶数前c++

在C++中，可以使用两个指针分别遍历给定的单链表，一个指针每次移动两步（处理偶数节点），另一个指针每次移动一步（处理奇数节点）。当遇到奇数节点时，我们可以将它插入到当前偶数节点之后。下面是简单的步骤描述：

1. 定义两个指针`prev`（初始为NULL）、`curr`（指向头节点）和`odd`（初始化为NULL）。
2. 当`curr`不为空时，进入循环：
a. 检查`curr->next`是否为NULL。如果是，则说明已经到达链表末尾，直接返回原链表。
b. 如果`curr`是奇数节点（检查`curr`是否为NULL），则复制`curr`节点并将其插入到`prev`之后，然后更新`prev`为`curr`，`curr`为`curr->next`。
c. 否则是偶数节点，直接移动`curr`到下一个节点，`prev`保持不变。
3. 循环结束后，`prev`就是新的头节点，原来的头节点变为`prev->next`。

以下是一个简化的伪代码示例：

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

ListNode* oddEvenList(ListNode* head) {
    if (head == NULL || head->next == NULL) return head;

    ListNode* odd = nullptr;
    ListNode* even = head;
    ListNode* prev = nullptr;

    while (even != nullptr && even->next != nullptr) {
        odd = odd ? odd->next : head;
        prev = even;
        even = even->next->next;

        // 插入奇数节点到当前偶数节点后
        if (odd != nullptr) {
            ListNode* temp = odd;
            odd = odd->next;
            prev->next = temp;
            temp->next = even;
        }
    }

    // 如果链表长度为奇数，最后的节点需要特殊处理
    if (odd != nullptr) {
        prev->next = odd;
    }

    return head;
}