链表排序--(奇数位是升序，偶数位是降序)

题目描述

对一个单链表进行排序，但这个链表有一个特殊的结构：

奇数位是升序：链表中位于奇数位置的节点是按升序排列的。例如，如果链表的第1个节点的值是1，第3个节点的值是3，第5个节点的值是5，那么这些值是按升序排列的。

偶数位是降序：链表中位于偶数位置的节点是按降序排列的。例如，如果链表的第2个节点的值是8，第4个节点的值是6，第6个节点的值是4，那么这些值是按降序排列的。

示例

假设我们有一个链表如下：

1 -> 8 -> 3 -> 6 -> 5 -> 4 -> nullptr

● 奇数位：第1个节点是1，第3个节点是3，第5个节点是5。这些节点的值是 1, 3, 5，它们是升序的。

● 偶数位：第2个节点是8，第4个节点是6，第6个节点是4。这些节点的值是 8, 6, 4，它们是降序的。

排序目标

要将这个链表重新排列成一个完全升序的链表

思路分析

分离链表：首先将链表分成两个链表，一个包含奇数位节点，另一个包含偶数位节点。

反转偶数位链表：由于偶数位是降序的，我们可以将偶数位链表反转，使其变为升序。

合并链表：将两个升序的链表合并成一个完全升序的链表。

分离链表

反转偶数位链表

合并两个有序链表

最终排序结果

对于上面的示例链表，排序后的链表应该是：

1 -> 3 -> 4 -> 5 -> 6 -> 8 -> nullptr

这个链表中的所有节点都是按升序排列的。

完整代码

#include <iostream>
using namespace std;

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

// 分离链表为奇数位和偶数位
pair<ListNode*, ListNode*> splitList(ListNode* head) {
    ListNode* oddHead = nullptr;
    ListNode* evenHead = nullptr;
    ListNode* oddTail = nullptr;
    ListNode* evenTail = nullptr;
    int index = 1;

    while (head) {
        if (index % 2 == 1) { // 奇数位
            if (!oddHead) {
                oddHead = head;
                oddTail = head;
            }
            else {
                oddTail->next = head;
                oddTail = oddTail->next;
            }
        }
        else { // 偶数位
            if (!evenHead) {
                evenHead = head;
                evenTail = head;
            }
            else {
                evenTail->next = head;
                evenTail = evenTail->next;
            }
        }
        head = head->next;
        index++;
    }

    if (oddTail) oddTail->next = nullptr;
    if (evenTail) evenTail->next = nullptr;

    return { oddHead, evenHead };
}

// 反转链表
ListNode* reverseList(ListNode* head) {
    auto newhead = new ListNode(0);
    auto p = head;
    while (p) {
        auto q = p->next;
        p->next = newhead->next;
        newhead->next = p;
        p = q;
    }
    return newhead->next;
}

// 合并两个升序链表
ListNode* mergeLists(ListNode* l1, ListNode* l2) {
    auto newhead = new ListNode(0);
    auto tail = newhead;

    while (l1 && l2) {
        if (l1->val < l2->val) {
            tail->next = l1;
            l1 = l1->next;
        }
        else {
            tail->next = l2;
            l2 = l2->next;
        }
        tail = tail->next;
    }

    tail->next = l1 ? l1 : l2;

    return newhead->next;
}

// 主函数：对链表进行排序
ListNode* sortLinkedList(ListNode* head) {
    if (!head || !head->next) return head;

    // 保存 splitList 的结果
    pair<ListNode*, ListNode*> splitResult = splitList(head);
    ListNode* oddHead = splitResult.first;   // 提取奇数位链表
    ListNode* evenHead = splitResult.second; // 提取偶数位链表
   

    // 反转偶数位链表
    evenHead = reverseList(evenHead);

    // 合并两个升序链表
    return mergeLists(oddHead, evenHead);
}

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

// 测试代码
int main() {
    ListNode* head = new ListNode(1);
    head->next = new ListNode(8);
    head->next->next = new ListNode(3);
    head->next->next->next = new ListNode(6);
    head->next->next->next->next = new ListNode(5);
    head->next->next->next->next->next = new ListNode(4);

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

    ListNode* sortedHead = sortLinkedList(head);

    cout << "Sorted List: ";
    printList(sortedHead);

    return 0;
}