33-奇偶链表

自己的做法

算法思想

维护两个虚链表，一个是奇数项组成的链表，一个是偶数项组成的链表。

之所以叫虚链表，是因为并没有创建新的节点，是在原来的链表上虚拟出来的。

使用指针cur遍历链表，但是cur每次走两步，也就是cur只会指向奇数项节点。

然后将该奇数项节点和其后的偶数项节点分别插入到两个虚链表的尾部。

因为奇数项链表一定在偶数项链表之前。

所以对于奇数项链表，只需要维护一个指向尾节点的指针odd即可；

对于偶数项链表，因为每次插入一个奇数项节点，都需要连接到后面的偶数项节点的头部，所以需要维护两个指针：

even_head和even_tail，即链表头部和尾部。

算法实现

class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        if(head == nullptr || head->next == nullptr) {
            return head;
        }
        ListNode * odd = head;              //奇数链表尾部
        ListNode * even_head = head->next;  //偶数链表头部
        ListNode * even_tail = head->next;  //偶数链表尾部

        ListNode * cur = head->next->next;
        while (cur) {
            ListNode * temp = cur->next && cur->next->next ? cur->next->next : nullptr;
            even_tail->next = cur->next;
            cur->next =even_head;
            odd->next = cur;

            odd = odd->next;
            even_tail = even_tail->next;
            cur = temp;
        }
        return head;
    }
};

注：第13行temp赋值，也可以去掉对cur->next->next的判空。

性能分析

时间复杂度：遍历链表，$O(n)$。

空间复杂度：$O(1)$。

参考做法

算法思想

物理分成两个链表，一个奇数链表，一个偶数链表，然后再将两个链表连接起来。

整个链表头节点就是奇数链表头节点，oddHead指针指向该节点；

链表头节点的下一个节点就是偶数链表头节点，evenHead指针指向该节点。

然后使用odd和even两个指针分别进行迭代，初始，odd指向oddHead，even指向evenHead。

然后：

1. 首先连接奇数节点，even的下一个节点就是奇数链表的下一个要连接的节点，即odd->next = even->next，然后odd = odd->next
2. 然后链接偶数节点，此时odd的下一个节点就是偶数链表要连接的下一个节点，即even->next = odd->next，然后even->next

迭代结束的条件是：even == null || even->next == null。

因为：

如果总节点数为2n，则奇偶节点各n个，且偶节点是尾节点，所以当even指向尾节点时，迭代结束，此时odd指向最后一个奇数节点；

总节点为2n + 1时，偶节点有n个，奇数节点有n + 1个，且奇数节点是尾节点，所以当even为空时，迭代结束，此时odd同样指向最后一个奇数节点。

最后将两个链表连接起来即可。

算法实现

class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        if(head == nullptr || head->next == nullptr) {
            return head;
        }
        ListNode * oddHead = head;              //奇数链表
        ListNode * evenHead = head->next;  //偶数链表
        ListNode * odd = oddHead;
        ListNode * even = evenHead;

        while (even && even->next) {
            odd->next = even->next;
            odd = odd->next;

            even->next = odd->next;
            even = even->next;
        }
        odd->next = evenHead;
        return head;
    }
};

性能分析

时间复杂度：$O(n)$。

空间复杂度：$O(1)$。