奇偶链表

题目链接

给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。

请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。

示例:

输入: 1->2->3->4->5->NULL
输出: 1->3->5->2->4->NULL

思路

解法一：

可将整个过程分为如下三步：

  1. 连接奇数节点链表
  2. 连接偶数节点链表
  3. 将上面的两个链表相连

其中，前两个步骤各需要一个指针指向头结点，且需要注意指针移动的顺序。

全部节点分离完毕的条件是 even 为空节点或者 even.next 为空节点，此时 odd 指向最后一个奇数节点（即奇数链表的最后一个节点）。

  • 当为偶数个节点时，最后结果是 even 不为空，even->next 为空，所以循环条件为 even->next != nullptr
  • 当为奇数个节点时，最后 even 为空，所以循环条件为 even != nullptr
  • 以上两个条件都要满足。
class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        if (head == nullptr) {
            return head;
        }
        ListNode* evenNode = head->next; // 偶数节点
        ListNode* odd = head; //奇数节点
        ListNode *even = evenNode;
        while (even != nullptr && even->next != nullptr) { // 保证都不为空
            odd->next = even->next;
            odd = odd->next;
            even->next = odd->next;
            even = even->next;
        }
        odd->next = evenNode;
        return head;
    }
};