公司网站做的比较好,安徽淮北做网站的公司,备案 网站 收录,wordpress没有编辑器文章目录 前言题目解决方案一1.1 思路阐述1.2 源码 解决方案二2.1 思路阐述2.2 源码 总结 前言
这道题算是链表思路的一种常规题#xff0c;看透题目本质做起来还是不难。 题目
描述 给定一个单链表#xff0c;请设定一个函数#xff0c;将链表的奇数位节点和偶数位节点分… 文章目录 前言题目解决方案一1.1 思路阐述1.2 源码 解决方案二2.1 思路阐述2.2 源码 总结 前言
这道题算是链表思路的一种常规题看透题目本质做起来还是不难。 题目
描述 给定一个单链表请设定一个函数将链表的奇数位节点和偶数位节点分别放在一起重排后输出。 注意是节点的编号而非节点的数值。
数据范围节点数量满足 0 ≤ n ≤ 1 0 5 0≤n≤10^5 0≤n≤105节点中的值都满足 0 ≤ v a l ≤ 1000 0≤val≤1000 0≤val≤1000 要求空间复杂度 O ( n ) O(n) O(n)时间复杂度 O ( n ) O(n) O(n) 示例1 输入
{1,2,3,4,5,6}
返回值
{1,3,5,2,4,6}
说明
1-2-3-4-5-6-NULL 重排后为 1-3-5-2-4-6-NULL
示例2 输入
{1,4,6,3,7}
返回值
{1,6,7,4,3}
说明
1-4-6-3-7-NULL 重排后为 1-6-7-4-3-NULL 奇数位节点有1,6,7偶数位节点有4,3。重排后为1,6,7,4,3
解决方案一
1.1 思路阐述
题目要求的空间复杂度并没有限制为 O ( 1 ) O(1) O(1)所以可以考虑用一个辅助的链表来做。
因为最后的结果是把奇节点放一起再放偶节点所以我可以把原来链表中所有的奇节点和偶节点都取出来先取奇节点再取偶节点取出来的节点一次插入到辅助链表中去。
最后输出辅助链表对应的节点即可。
1.2 源码
/*** struct ListNode {* int val;* struct ListNode *next;* ListNode(int x) : val(x), next(nullptr) {}* };*/
class Solution {public:/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可*** param head ListNode类* return ListNode类*/ListNode* oddEvenList(ListNode* head) {// write code hereListNode* newList new ListNode(-1);ListNode* rec newList;ListNode* tempHead head;int count 0;if (!head)return nullptr;while (head) {count;//取奇数节点并插入if (count % 2 ! 0) {ListNode* temp new ListNode(head-val);rec-next temp;rec temp;head head-next;} else {head head-next;}}headtempHead;count0;//重置计数器后取偶数节点并插入while (head) {count;//插入偶数if (count % 2 0) {ListNode* temp new ListNode(head-val);rec-next temp;rec temp;head head-next;} else {head head-next;}}return newList-next;}
};解决方案二
2.1 思路阐述
对于链表题的思路除了上面的开辟辅助链表(或者其他的辅助数组)通常还采用双指针来做。
如下图所示第一个节点是奇数位第二个节点是偶数第二个节点后又是奇数位因此可以断掉节点1和节点2之间的连接指向节点2的后面即节点3如红色箭头。如果此时我们将第一个节点指向第三个节点就可以得到那么第三个节点后为偶数节点因此我们又可以断掉节点2到节点3之间的连接指向节点3后一个节点即节点4如紫色箭头。那么我们再将第二个节点指向第四个节点又回到刚刚到情况了。 2.2 源码
/*** struct ListNode {* int val;* struct ListNode *next;* ListNode(int x) : val(x), next(nullptr) {}* };*/
class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可** * param head ListNode类 * return ListNode类*/ListNode* oddEvenList(ListNode* head) {if(!head)return nullptr;ListNode* oddhead;ListNode* evenhead-next;ListNode*tempEveneven;while (eveneven-next) {odd-nexteven-next;oddodd-next;even-nextodd-next;eveneven-next;}odd-nexttempEven;return head;}
};总结
链表做题两种方式双指针开辟辅助数组或链表。
