链表的奇偶重排

[编程题]链表的奇偶重排

热度指数：101459 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个单链表，请设定一个函数，将链表的奇数位节点和偶数位节点分别放在一起，重排后输出。

注意是节点的编号而非节点的数值。

数据范围：节点数量满足 $0 \le n \le 10^5$ ，节点中的值都满足 $0 \le val \le 1000$

要求：空间复杂度 $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

备注:

链表长度不大于200000。每个数范围均在int内。

说明：本题目包含复杂数据结构ListNode，点此查看相关信息

算法知识视频讲解

牛客题解官

发表于 2022-04-22 11:35:10

精华题解题目主要信息: 给定一个链表，将奇数位的节点依次连在前半部分，偶数位的节点依次连在后半部分返回连接后的链表头举一反三：学习完本题的思路你可以解决如下题目： BM4.合并有序链表 BM5.合并k个已排序的链表 BM6.判断链表中是否有环 BM7.链表中环的入口节点 BM8.链表中倒数最后k个展开全文

LifelongCode

发表于 2021-01-07 12:20:37

转载：作者：LeetCode-Solution链接：https://leetcode-cn.com/problems/odd-even-linked-list/solution/qi-ou-lian-biao-by-leetcode-solution/来源：力扣（LeetCode）方法一：分离节展开全文

天上掉下来SCI

发表于 2022-04-07 21:00:28

不敢相信这么顺利，大概就写了一会儿，，，我现在对于这种题已经这么熟练了吗？真开心哈哈哈哈哈。 * struct ListNode { * int val; * struct ListNode *next; * }; * * C语言声明定义全局变量请加上static，防止重复定义 */ 展开全文

摸鱼学大师

发表于 2022-02-24 20:24:20

题目主要信息: 给定一个链表，将奇数位的节点依次连在前半部分，偶数位的节点依次连在后半部分返回连接后的链表头具体思路: 如下图所示，第一个节点是奇数位，第二个节点是偶数，第二个节点后又是奇数位，因此可以断掉节点1和节点2之间的连接，指向节点2的后面即节点3，如红色箭头。如果此时我们将第一个节展开全文

牛客516598323号

发表于 2020-09-22 21:50:59

一样，链表题需要投机取巧，使用数组加快运算。第一遍遍历链表分拣出奇偶结点的值，然后第二遍遍历把重新排序好的值送回去就行。用例通过率: 100.00% 运行时间: 963ms 占用内存: 40996KB。 # class ListNode: # def __init__(self, x): # 展开全文