数据结构与算法-8.奇偶链表
2021/10/30 12:10:16
本文主要是介绍数据结构与算法-8.奇偶链表,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
8、奇偶链表
题目
给定一个单链表,把所有的奇数节点和偶数节点分别排在一起。请注意,这里的奇数节点和偶数节点指的是节点编号的奇偶性,而不是节点的值的奇偶性。
请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1),时间复杂度应为 O(nodes),nodes 为节点总数。
示例 1:
输入: 1->2->3->4->5->NULL
输出: 1->3->5->2->4->NULL
示例 2:
输入: 2->1->3->5->6->4->7->NULL
输出: 2->3->6->7->1->5->4->NULL
- 应当保持奇数节点和偶数节点的相对顺序。
- 链表的第一个节点视为奇数节点,第二个节点视为偶数节点,以此类推。
struct ListNode { int val; ListNode* next; ListNode() : val(0), next(nullptr) {} ListNode(int x) : val(x), next(nullptr) {} ListNode(int x, ListNode* next) : val(x), next(next) {} };
8.0、直接解法
生成两个新链表,现在开始遍历原链表,遍历到奇数就把这个节点添加到奇链表后,遍历到偶数就把这个节点添加到偶链表后。
【1,2,3,4,5,6,7,8】
奇链表:【1,3,5,7】
偶链表:【2,4,6,8】
最后把两个链表拼接起来为
【1,3,5,7,2,4,6,8】
- 时间复杂度:O(n)
- 空间复杂度:O(n)
8.1、一般用法(最常用)
对于链表【1,2,3,4,5,6,7,8】
创建两个指针a,b初始指向1,2
- a . next = b . next a的下一个指向b的下一个也就是3
- a = a . next a指向3
- b . next = a . next b的下一个指向a的下一个也就是4
- b = b . next b指向4
- 以此类推
在最初需要记录2的索引,因为2是偶链表的开始,最后需要将奇链表的尾与偶链表的首拼接在一起。
ListNode* oddEvenList1(ListNode* head) { if (!head || !head->next)return head; //节点为空或者只有一个直接返回 ListNode* tail = head->next; ListNode* oddNode = head; //奇节点 ListNode* evenNode = head->next; //偶节点 while (evenNode && evenNode->next) { oddNode->next = evenNode->next; oddNode = oddNode->next; evenNode->next = oddNode->next; evenNode = evenNode->next; } oddNode->next = tail; return head; }
- 时间复杂度:O(n)
- 空间复杂度:O(1)
这篇关于数据结构与算法-8.奇偶链表的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-02springboot项目无法注册到nacos-icode9专业技术文章分享
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)