链表排序--(奇数位是升序，偶数位是降序)
题目描述
对一个单链表进行排序，但这个链表有一个特殊的结构：
奇数位是升序：链表中位于奇数位置的节点是按升序排列的。例如，如果链表的第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;
}
运行结果
