题目
描述
给定一个单链表，请设定一个函数，将链表的奇数位节点和偶数位节点分别放在一起，重排后输出。
注意是节点的编号而非节点的数值。
数据范围：节点数量满足 0≤n≤10^5，节点中的值都满足 0≤val≤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 内。
分析
分析特殊情况
由题意，我们容易得出如下的结论：
分析一般情况
一种比较容易想到的思路如下：
在开始处理时，我们知道链表头指向的是第一个奇数链的末尾，接下来我们每次遍历两个元素，我们只需要将下一个奇数位置的元素插入到这个奇数链末尾即可，然后更新新的奇数链末尾，等待下一次插入，等到处理结束，从表头到奇数链末尾就是所有奇数位置的元素，奇数链末尾到链表末尾就是所有偶数链的元素。
使用了 pOddEnd 和 pNextOdd。
另一种双指针法：
第一个节点是奇数位，第二个节点是偶数，第二个节点后又是奇数位，因此可以断掉节点 1 和节点 2 之间的连接，指向节点 2 的后面即节点 3，如红色箭头。如果此时我们将第一个节点指向第三个节点，就可以得到那么第三个节点后为偶数节点，因此我们又可以断掉节点 2 到节点 3 之间的连接，指向节点 3 后一个节点即节点 4，如蓝色箭头。那么我们再将第二个节点指向第四个节点，又回到刚刚到情况了。
step 1：判断空链表的情况，如果链表为空，不用重排。
step 2：使用双指针 odd 和 even 分别遍历奇数节点和偶数节点，并给偶数节点链表一个头。
step 3：上述过程，每次遍历两个节点，且 even 在后面，因此每轮循环用 even 检查后两个元素是否为 NULL，如果不为再进入循环进行上述连接过程。
step 4：将偶数节点头接在奇数最后一个节点后，再返回头部。
代码示例
示例一：
pOddEnd 初始化为头节点，pCur 为当次的 NextOdd，找到当前的 pNextOdd，然后将 pCur 插入到 pOddEnd 处，使用 pNextOdd 更新 pCur，直到 pCur 为空，即到达链表末尾。
/** * 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 here if(nullptr == head || nullptr == head->next || nullptr == head->next->next){ return head; }
ListNode* pOddEnd = head; ListNode* pPre = head->next; ListNode* pCur = pPre->next; ListNode* pNextOdd = nullptr;
while(nullptr != pCur){ // update the pPre and pNextOdd pPre->next = pCur->next; pPre = pPre->next; if(nullptr != pPre){ pNextOdd = pPre->next; }else{ pNextOdd = nullptr; } // insert thr pCur to Odd list rear pCur->next = pOddEnd->next; pOddEnd->next = pCur; pOddEnd = pOddEnd->next;
pCur = pNextOdd; }
return head; }};
复制代码
示例二：
如上面解答中所说，这里需要多注意一点，要预先保存一下偶数链的头节点 head2，之后需要将奇数链的末尾连接过来。
/** * 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 here if(nullptr == head || nullptr == head->next || nullptr == head->next->next){ return head; }
ListNode* pOdd = head; ListNode* pEven = pOdd->next; ListNode* head2 = pEven;
while(nullptr != pEven && nullptr != pEven->next){ pOdd->next = pEven->next; pOdd = pOdd->next; pEven->next = pOdd->next; pEven = pEven->next; } pOdd->next = head2;
return head; }};
复制代码
评论