328 奇偶链表

328. 奇偶链表 - 力扣（LeetCode）
优质题解：奇偶链表 - 奇偶链表 - 力扣（LeetCode）

题目

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

输入: head = [1,2,3,4,5]
输出: [1,3,5,2,4]

输入: head = [2,1,3,5,6,4,7]
输出: [2,3,6,7,1,5,4]

数据结构

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        //todo
    }
};

解法：迭代

输入： 1 --> 2 --> 3 --> 4 --> 5
输出： 1 --> 3 --> 5 --> 2 --> 4

思考过程

1. 列出输入和输出，进行思考
2. 涉及到局部断链，肯定要保存原始键，优先考虑双指针来保存。
3. 问题本质是：奇数节点连在一起；偶数节点连在一起；然后再串起来
   1. 1 --> 3 --> 5
   2. 2 --> 4 --> nullptr
   3. 然后5 --> 2
4. 刚好，双指针一个指向奇数节点、另一个指向偶数节点
5. 开始考虑第一轮：odd = 1、even = 2
   1. 挂接奇数节点的下一个：odd->next = even->next，即1->next = 2->next = 3
   2. 挂接偶数节点的下一个：even->next = even->next->next，即2->next = 2->next->next = 4
   3. 位移双指针，进入下一轮
      1. odd = odd->next，即odd = 3
      2. even = even->next，即even = 4
6. 下一轮和上一轮一样运行，自己手算看下对不对
7. 考虑循环体中止情况
   1. 循环体内有访问内存的操作，even->next和even->next->net，因此条件就是这两个不能为空
8. 考虑循环体外部
   1. 自己手算一遍循环体，发现还未将奇数、偶数链挂接起来
   2. 偶数链的开头即even_head = head->next，这个要事先保存下来，不然断链操作会导致丢失next
   3. 奇数链的开头即head指针，不会变。因此，退出循环体之后，odd->next = even_head
9. 考虑返回值
   1. 奇数链的开头即head，返回head即可
10. 最后，考虑在边界条件下，此逻辑是否满足，不满足需要再加额外的判断。根据特例逐一考虑即可，多加条件也没关系，肯定没错的，反而还更保险

class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        //边界条件
        if(head == nullptr) return head;
        if(head->next == nullptr) return head;
        if(head->next->next == nullptr) return head; //细想一下，这个条件可以不加的。但你加上也没事，反而更保险

        //记录下偶数链的头
        ListNode* even_head = head->next;

        ListNode* odd = head;           //奇数链的指针
        ListNode* even = head->next;    //偶数链的指针
        while(even && even->next) {     //保证循环体内，访问内存的操作不崩溃即可
            odd->next = even->next;
            even->next = even->next->next;

            //下一个状态
            odd = odd->next;
            even = even->next;
        }

        //将奇数链、偶数链，挂接起来
        odd->next = even_head;

        //奇数链的开头即是原来的head，没有变过
        return head;
    }
};

【时间复杂度】本质上循环体内，只对链表遍历了一次，即O(n)
【空间复杂度】常数项，O(1)