引言
在C/C++面试过程中，链表一向是考察的重点，常见的有链表排序、链表输出、链表的增删查改等内容，本节以一个链表的奇数位节点和偶数位节点作为示例，引出链表的特殊输出方式。
需求描述
给定一个单链表，请设定一个函数，将链表的奇数位节点和偶数位节点分别放在一起，重排后输出。
注意是节点的编号而非节点的数值。
要求：空间复杂度
O(n)O(n)
，时间复杂度
O(n)O(n)
测试用例1
输入：
{1,2,3,4,5,6}
复制
返回值：
{1,3,5,2,4,6}
复制
说明：
1-3-5-2-4-6-NULL
测试用例2
输入：
{1,4,6,3,7}
复制
返回值：
{1,6,7,4,3}
复制
说明：
1-6-7-4-3-NULL奇数位节点有1,6,7，偶数位节点有4,3。重排后为1,6,7,4,3
备注：
链表长度不大于。每个数范围均在int内。
思路分析
如下图所示，第一个节点是奇数位，第二个节点是偶数，第二个节点后又是奇数位，因此可以断掉节点1和节点2之间的连接，指向节点2的后面即节点3，如红色箭头。如果此时我们将第一个节点指向第三个节点，就可以得到那么第三个节点后为偶数节点，因此我们又可以断掉节点2到节点3之间的连接，指向节点3后一个节点即节点4，如蓝色箭头。那么我们再将第二个节点指向第四个节点，又回到刚刚到情况了。
step1：判断空链表的情况，如果链表为空，不用重排。
step2：使用双指针odd和even分别遍历奇数节点和偶数节点，并给偶数节点链表一个头。
step3：上述过程，每次遍历两个节点，且even在后面，因此每轮循环用even检查后两个元素是否为NULL，如果不为再进入循环进行上述连接过程。
step4：将偶数节点头接在奇数最后一个节点后，再返回头部。
具体过程可以参考如下图示：
购买专栏解锁剩余40%