[链表] 奇偶链表
328. 奇偶链表 - 力扣(LeetCode)
优质题解:奇偶链表 - 奇偶链表 - 力扣(LeetCode)
题目
给定一个单链表,把所有的奇数节点和偶数节点分别排在一起。请注意,这里的奇数节点和偶数节点指的是节点编号的奇偶性,而不是节点的值的奇偶性。
输入: head = [1,2,3,4,5]
输出: [1,3,5,2,4]输入: head = [2,1,3,5,6,4,7]
输出: [2,3,6,7,1,5,4]
数据结构
/*** Definition for singly-linked list.* 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) {}* };*/
class Solution {
public:ListNode* oddEvenList(ListNode* head) {//todo}
};
解法:迭代
输入: 1 --> 2 --> 3 --> 4 --> 5
输出: 1 --> 3 --> 5 --> 2 --> 4
思考过程
- 列出输入和输出,进行思考
- 涉及到局部断链,肯定要保存原始键,优先考虑双指针来保存。
- 问题本质是:奇数节点连在一起;偶数节点连在一起;然后再串起来
1 --> 3 --> 5
2 --> 4 --> nullptr
- 然后
5 --> 2
- 刚好,双指针一个指向奇数节点、另一个指向偶数节点
- 开始考虑第一轮:
odd = 1
、even = 2
- 挂接奇数节点的下一个:
odd->next = even->next
,即1->next = 2->next = 3
- 挂接偶数节点的下一个:
even->next = even->next->next
,即2->next = 2->next->next = 4
- 位移双指针,进入下一轮
odd = odd->next
,即odd = 3
even = even->next
,即even = 4
- 挂接奇数节点的下一个:
- 下一轮和上一轮一样运行,自己手算看下对不对
- 考虑循环体中止情况
- 循环体内有访问内存的操作,
even->next
和even->next->net
,因此条件就是这两个不能为空
- 循环体内有访问内存的操作,
- 考虑循环体外部
- 自己手算一遍循环体,发现还未将奇数、偶数链挂接起来
- 偶数链的开头即
even_head = head->next
,这个要事先保存下来,不然断链操作会导致丢失next
- 奇数链的开头即
head
指针,不会变。因此,退出循环体之后,odd->next = even_head
- 考虑返回值
- 奇数链的开头即
head
,返回head
即可
- 奇数链的开头即
- 最后,考虑在边界条件下,此逻辑是否满足,不满足需要再加额外的判断。根据特例逐一考虑即可,多加条件也没关系,肯定没错的,反而还更保险
class Solution {
public:ListNode* oddEvenList(ListNode* head) {//边界条件if(head == nullptr) return head;if(head->next == nullptr) return head;if(head->next->next == nullptr) return head; //细想一下,这个条件可以不加的。但你加上也没事,反而更保险//记录下偶数链的头ListNode* even_head = head->next;ListNode* odd = head; //奇数链的指针ListNode* even = head->next; //偶数链的指针while(even && even->next) { //保证循环体内,访问内存的操作不崩溃即可odd->next = even->next;even->next = even->next->next;//下一个状态odd = odd->next;even = even->next;}//将奇数链、偶数链,挂接起来odd->next = even_head;//奇数链的开头即是原来的head,没有变过return head;}
};
【时间复杂度】本质上循环体内,只对链表遍历了一次,即O(n)
【空间复杂度】常数项,O(1)
[链表] 奇偶链表
328. 奇偶链表 - 力扣(LeetCode)
优质题解:奇偶链表 - 奇偶链表 - 力扣(LeetCode)
题目
给定一个单链表,把所有的奇数节点和偶数节点分别排在一起。请注意,这里的奇数节点和偶数节点指的是节点编号的奇偶性,而不是节点的值的奇偶性。
输入: head = [1,2,3,4,5]
输出: [1,3,5,2,4]输入: head = [2,1,3,5,6,4,7]
输出: [2,3,6,7,1,5,4]
数据结构
/*** Definition for singly-linked list.* 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) {}* };*/
class Solution {
public:ListNode* oddEvenList(ListNode* head) {//todo}
};
解法:迭代
输入: 1 --> 2 --> 3 --> 4 --> 5
输出: 1 --> 3 --> 5 --> 2 --> 4
思考过程
- 列出输入和输出,进行思考
- 涉及到局部断链,肯定要保存原始键,优先考虑双指针来保存。
- 问题本质是:奇数节点连在一起;偶数节点连在一起;然后再串起来
1 --> 3 --> 5
2 --> 4 --> nullptr
- 然后
5 --> 2
- 刚好,双指针一个指向奇数节点、另一个指向偶数节点
- 开始考虑第一轮:
odd = 1
、even = 2
- 挂接奇数节点的下一个:
odd->next = even->next
,即1->next = 2->next = 3
- 挂接偶数节点的下一个:
even->next = even->next->next
,即2->next = 2->next->next = 4
- 位移双指针,进入下一轮
odd = odd->next
,即odd = 3
even = even->next
,即even = 4
- 挂接奇数节点的下一个:
- 下一轮和上一轮一样运行,自己手算看下对不对
- 考虑循环体中止情况
- 循环体内有访问内存的操作,
even->next
和even->next->net
,因此条件就是这两个不能为空
- 循环体内有访问内存的操作,
- 考虑循环体外部
- 自己手算一遍循环体,发现还未将奇数、偶数链挂接起来
- 偶数链的开头即
even_head = head->next
,这个要事先保存下来,不然断链操作会导致丢失next
- 奇数链的开头即
head
指针,不会变。因此,退出循环体之后,odd->next = even_head
- 考虑返回值
- 奇数链的开头即
head
,返回head
即可
- 奇数链的开头即
- 最后,考虑在边界条件下,此逻辑是否满足,不满足需要再加额外的判断。根据特例逐一考虑即可,多加条件也没关系,肯定没错的,反而还更保险
class Solution {
public:ListNode* oddEvenList(ListNode* head) {//边界条件if(head == nullptr) return head;if(head->next == nullptr) return head;if(head->next->next == nullptr) return head; //细想一下,这个条件可以不加的。但你加上也没事,反而更保险//记录下偶数链的头ListNode* even_head = head->next;ListNode* odd = head; //奇数链的指针ListNode* even = head->next; //偶数链的指针while(even && even->next) { //保证循环体内,访问内存的操作不崩溃即可odd->next = even->next;even->next = even->next->next;//下一个状态odd = odd->next;even = even->next;}//将奇数链、偶数链,挂接起来odd->next = even_head;//奇数链的开头即是原来的head,没有变过return head;}
};
【时间复杂度】本质上循环体内,只对链表遍历了一次,即O(n)
【空间复杂度】常数项,O(1)