奇偶链表

1. 题目

给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。
请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。
示例 1:
输入: 1->2->3->4->5->NULL
输出: 1->3->5->2->4->NULL
示例 2:
输入: 2->1->3->5->6->4->7->NULL
输出: 2->3->6->7->1->5->4->NULL
说明:
应当保持奇数节点和偶数节点的相对顺序。
链表的第一个节点视为奇数节点，第二个节点视为偶数节点，以此类推。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/odd-even-linked-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 分析

题目的意思很简单就是按照下标将奇数下标的节点排列在前面，将偶数下标的值排列在后面。题目意思很简单，但是如何将这个问题解决呢？

想法很简单，就是指针的摆动，但是别忘了temp保存上图中2这个节点，即每次都是odd节点的后一个，这样的话才会将偶数一直连起来。同时在每次向前行进过程中指针之间进行运作。整体的流程是：odd节点指针指向even节点的下一个节点，然后even节点指向odd节点下一个的下一个。然后依次循环即可，但是注意在行进过程中要保持even != null && even.next != null具体的原因，可以自己画一画，如果不确保这样的话，下一轮迭代odd.next到了even.next的的位置，但even又要到odd.next.next的位置，此时如果不确保even.next != null则会抛出空指针异常行为！

3. 代码实现

    /**
     * 按照节点的奇偶属性将节点按照前面奇数后面偶数的排列
     * 2->1->3->5->6->4->7
     * ==>
     * 2->3->6->7->1->5->4
     */
    public ListNode oddEvenList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        // 设立奇偶节点
        ListNode odd = head;
        ListNode even = odd.next;
        // 这里主要是注意链表节点连接的时机问题
        while (even != null && even.next != null) {
            ListNode temp = odd.next; // 保存临时节点
            odd.next = even.next; // odd开始修改指向
            odd = odd.next; // odd开始向后行进
            even.next = odd.next; // even开始修改指向
            odd.next = temp; // 为了确保奇数后面是偶数节点，此时需要将temp连接上
            even = even.next; // 最后even向前行进
        }
        return head;
    }

小结

题目以前做过，不过今天做的时候因为是每日一题还稍微看了下，还好比较顺利的做出来了，链表的题目基本上只要你用笔可以画出来，用代码基本可以实现。

Keep coding, keep thinking! 2020-11-13写于南京