题目描述

给定一个单链表，请设定一个函数，将链表的奇数位节点和偶数位节点分别放在一起，重排后输出。
注意是节点的编号而非节点的数值。

方法一 分解+组合

解题思路

可以新建两个辅助链表头，之后分别连接奇数位节点和偶数位节点，然后再把这两个链表组合起来得到结果。

代码示例

/**
 * 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) {
        // 边界情况
        if(head == NULL)
            return head;
        // 
        ListNode *odd_head = new ListNode(0), *even_head = new ListNode(0);
        ListNode *p = head, *op = odd_head, *ep = even_head;
        // 确定当前位置是奇数还是偶数
        int pos = 1;
        // 遍历原链表，把奇、偶节点放置在odd_head和even_head后
        while(p != NULL) {
            ListNode *t = p->next;
            // 当前位置为奇数
            if(pos % 2 == 1) {
                // 将该节点添加到op后
                op->next = p;
                op = op->next;
                op->next = NULL;
            }
            // 当前位置为偶数
            else {
                // 将该节点添加到ep后
                ep->next = p;
                ep = ep->next;
                ep->next = NULL;
            }
            // 更新p的位置和计数器pos
            p = t;
            pos++;
        }

        // 将偶数节点拼接到奇数节点之后
        op->next = even_head->next;
        // free掉之前新开的两个节点
        even_head->next = NULL;
        free(even_head);
        odd_head->next = NULL;
        free(odd_head);
        return head;
    }
};

复杂度分析

• 时间复杂度：需要遍历一遍链表，时间复杂度为
• 空间复杂度：只需要新建两个辅助节点，故空间复杂度为

方法二 奇偶双指针+定位符

解题思路

方法一需要新建两个辅助节点，可以考虑通过两个指针和一个定位符来代替，减少代码长度。
具体来说，定义奇指针odd和偶指针even以及偶数定位符evenHead。通过迭代的方式将奇数节点和偶数节点分离成两个链表，每一步首先更新奇数节点，然后更新偶数节点。更新方法如图示。

even为空或者even->next为空时，退出循环，合并分离好的链表。

代码示例

/**
 * 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) {
        // 边界情况
        if(head == NULL)
            return head;

        ListNode* evenHead = head->next; // 定位符
        ListNode* odd = head; // 奇指针
        ListNode* even = evenHead; // 偶指针
        // 遍历链表
        while (even != NULL && even->next != NULL) {
            // 更新奇指针
            odd->next = even->next;
            odd = odd->next;
            // 更新偶指针
            even->next = odd->next;
            even = even->next;
        }

        // 将偶数节点拼接到奇数节点之后
        odd->next = evenHead;
        return head;
    }
};

复杂度分析

• 时间复杂度：需要遍历一遍链表，时间复杂度为
• 空间复杂度：只需要维护有限个指针，故空间复杂度为