LeetCode 328. 奇偶链表(Odd Even Linked List)
2024-08-31 14:57:05
题目描述
给定一个单链表,把所有的奇数节点和偶数节点分别排在一起。请注意,这里的奇数节点和偶数节点指的是节点编号的奇偶性,而不是节点的值的奇偶性。
请尝试使用原地算法完成。你的算法的空间复杂度应为 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
说明:
- 应当保持奇数节点和偶数节点的相对顺序。
- 链表的第一个节点视为奇数节点,第二个节点视为偶数节点,以此类推。
解题思路
分别记录奇偶链表的首节点,其中偶链表的头节点分开记录,然后从偶链表头节点的下一个节点开始遍历,按照奇偶位置分别拼接到奇偶链表中,最后将偶链表的头节点拼接到奇链表的末尾,然后将偶链表的最后一个节点的next指针置为空。
代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* oddEvenList(ListNode* head) {
if(head == NULL || head->next == NULL || head->next->next == NULL) return head;
ListNode *odd = head, *even = head->next, *even_head = head->next, *right = head->next->next;
bool is_odd = true;
while(right){
if(is_odd){
odd->next = right;
odd = right;
right = right->next;
is_odd = false;
}
else{
even->next = right;
even = right;
right = right->next;
is_odd = true;
}
}
odd->next = even_head;
even->next = NULL;
return head;
}
};
最新文章
- ffmpeg获取文件的总时长(mp3/mp4/flv等)
- linux安装SVN
- rac one node在线relocation
- LeetCode 326
- iOS开发--TableView详细解释
- BZOJ3509: [CodeChef] COUNTARI
- chrome:// 的秘密!!一些有用的命令!
- Android studio 开发在真机测试
- [Swust OJ 188]--异面空间(读懂题意很重要)
- 浙江大学 pat 1006题解
- 201521123002《Java程序设计》第11周学习总结
- Python自建logging模块
- 学会这15点,让你分分钟拿下Redis数据库
- 6、jeecg 笔记之 自定义excel 模板导出(一)
- 利用ueditor保存到mysql数据库时出现乱码
- PHP isset 和 array_key_exists 对比
- ubuntu上编译linux内核
- Sql Server中的游标最好只用于有主键或唯一键的表
- python的redis简单使用
- golang多进程测试代码