C++ 排序奇升偶降链表
2022/1/12 11:05:32
本文主要是介绍C++ 排序奇升偶降链表,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
对于这题,可以先遍历一次,用队列保存递增的奇数位指针,用栈保存递减的偶数位指针。 这两个线性表输出的将都是递增的序列。那么逐个比较两个表的元素,然后小的先加入新链表,即可得出答案。 例如: 1->10->2->9->8->3->9->1 用队列保存1->2->8->9,再输出将是1->2->8->9 用栈保存10->9->3->1, 再输出将是1->3->9->10 那么得出答案1->1->2->3->8->9->9->10ListNode * HandleIt(queue<ListNode*>& ltr, stack<ListNode*>& rtl) { ListNode* p; if (ltr.front()->val > rtl.top()->val) { p = rtl.top(); rtl.pop(); } else { p = ltr.front(); ltr.pop(); } return p; } ListNode* sortLinkedList(ListNode* head) { if (!head->next) return head; //获得两条递增的线性表 queue<ListNode*> ltr;//从左向右递增 stack<ListNode*> rtl;//从右向左递增 bool isOdd = true;//是否奇数 while (head) { if (isOdd) { ltr.emplace(head); } else { rtl.emplace(head); } isOdd = !isOdd; head = head->next; } //找出新的链头 ListNode* newHead = HandleIt(ltr, rtl); ListNode* p = newHead; //对两个线性表进行整合排序 while (!ltr.empty() || !rtl.empty()) { if (ltr.empty()) { p->next = rtl.top(); rtl.pop(); } else if (rtl.empty()) { p->next = ltr.front(); ltr.pop(); } else { p->next = HandleIt(ltr, rtl); } p = p->next; } p->next = nullptr; return newHead; }
这篇关于C++ 排序奇升偶降链表的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-04el-table 开启定时器下,表格的选中状态会消失是什么原因-icode9专业技术文章分享
- 2024-10-03如何安装和初始化飞牛私有云 fnOS?-icode9专业技术文章分享
- 2024-10-03如何安装 App 并连接到飞牛 NAS?-icode9专业技术文章分享
- 2024-10-03如何安装飞牛 TV 并连接到影视服务器?-icode9专业技术文章分享
- 2024-10-03如何在PVE和ESXI上安装飞牛私有云 fnOS?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS安装系统异常情况处理-icode9专业技术文章分享
- 2024-10-03飞牛NAS如何创建存储空间?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS硬盘会自动休眠吗?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS如何安装飞牛影视和创建媒体库?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS如何为家人朋友开通影视账号?-icode9专业技术文章分享