用C++写，链表奇偶重排

在C++中，我们可以使用双指针法来实现链表中元素的奇偶重排。奇偶重排意味着将链表中的所有节点分为两部分，奇数位置的节点保持原顺序，偶数位置的节点按照递增顺序排列。以下是实现这一功能的一个基本步骤：

#include <iostream>
using namespace std;

// 链表节点定义
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

ListNode* oddEvenList(ListNode* head) {
    if (head == nullptr || head->next == nullptr) {
        return head;
    }
    
    // 定义两个指针，快慢指针
    ListNode *fast = head, *slow = head;
    ListNode *evenHead = nullptr, *evenTail = nullptr;
    
    // 快速移动到下一个偶数节点
    while (fast != nullptr && fast->next != nullptr) {
        fast = fast->next->next;  // 跳过两个节点
        if (fast == nullptr) break;
        
        // 慢速指针处理当前节点
        slow->next = evenHead ? evenHead : evenTail;  // 添加到偶数链表尾部
        if (evenTail != nullptr) evenTail->next = nullptr;  // 更新偶数链表尾部
        slow++;  // 移动到下一个节点

        evenTail = slow;  // 更新偶数链表尾部
    }

    // 将奇数链表连接回原链表的末尾
    if (evenHead != nullptr) {
        slow->next = evenHead;
    } else {
        slow->next = head;  // 如果只有奇数节点，直接接到原头
    }
    
    return head;
}

// 打印链表
void printList(ListNode* node) {
    while (node) {
        cout << node->val << " ";
        node = node->next;
    }
    cout << endl;
}

int main() {
    ListNode* head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);
    head->next->next->next = new ListNode(4);
    head->next->next->next->next = new ListNode(5);

    cout << "Original List: ";
    printList(head);

    head = oddEvenList(head);
    cout << "Reordered List: ";
    printList(head);

    return 0;
}

当你运行这个程序，它会首先打印原始链表，然后打印经过奇偶重排后的链表。