从青铜到王者：leetcode-奇偶链表

class Solution {
public:
    /**
    第一次观察：
    case1特点
    01： 头节点保持不变 输入前是1 ，输入后还是1
    02： 通过1节点找到2节点，奇数 就是1节点后面追加 最后一个节点就是2 3——>2 ,5 ->2.
         特点：都是在2前面，但是2位置并没有发生变化
    03：总结：链表特点：翻转后 节点 1 和节点 2位置都没有发生变化。移动是指针。
    04:在节点2之后插入也是如此。
    
    
    前提条件：链表 删除，和插入操作，必须清楚前面一个节点，才能保证整个链表不被破坏。
    
    思路：原地翻转 前提条件，
    1. 必须知道 前面一个节点。才能保证整个链表不被破坏。
    2. 至少有2个节点。

    第二次观察：
    01 按照上面步骤指向发现根本不对，
    02 发现只要 3 和 5 元素移走 就可以了。 偶数的根本不需要移动，自然就关联在一起了。

    思路原地翻转，
    
    步骤1 case1 为例子 奇数移动到前面，需要3个指针

    当前指针和 当前指前面一个指针。负责，删除一个节点。保证原来顺序不变
    奇数链表的最后一个位置，负责插入一个节点，保证原来顺序不变。

    步骤2:遍历时候 如果偶数位置，直接正常的移动。
    

   **/
    ListNode* oddEvenList(ListNode* head)
    {

        //约束条件：至少有2个节点。
        //也就是说，前面2个节点不需要翻转
        if (nullptr == head || nullptr == head->next || nullptr == head->next->next) {
            return head;
        }

        //01 定义 链表遍历需要3个数据结构

        ListNode* ptail1 = head; //插入的前面1个节点
        // ListNode* ptail2 =ptail1->next; //插入的前面1个节点

        ListNode* pcur = ptail1->next;
        ListNode* ppre = ptail1; // 删除单链表前，需要知道前面一个元素

        int i = 0;
        while (pcur) {
            //1(ptai1)->2(ptai2)->3(pcur)->4->5->NULL
            //奇数
            if (i & 1 == 1) {
                //1(ptail)-->2 --3（pcur）
                //1 ->3(ptail)-> 2
                ppre->next = pcur->next; //删除操作:单链表前，需要知道前面一个元素

                pcur->next = ptail1->next; //插入操作：需要知道插入节点前面一个位置，
                ptail1->next = pcur;
                ptail1 = pcur;

                pcur = ppre->next;

            } else {
                ppre = pcur;
                pcur = pcur->next;
            }
            i++;
        }

        return head;
    }
};

 /**
     *  借助三个辅助指针完成单链表翻转
     *  注意：这里是原地翻转，不需要建立新的节点。
     *   翻转后还是自己只不过head位置每次都发送变化，因此借助固定头节点方式。减少代码复杂度
     */
    ListNode* reverseList(ListNode* head)
    {
        if (nullptr == head || nullptr == head->next) {
            return head;
        }
        // ！！！！！！
        ListNode pHead(-1); //固定头节点插入
        pHead.next = head;
        //隐藏机制：第一个节点变成最后一个节点，元素位置并没有发送改变，因为单链表操作
        //因此我可以放心的默认第一个节点是已经排序号的。

        ListNode* pcur = head->next; //从第二个位置开始。
        ListNode* ppre = head;
        // 1->2(pcur)->3->4->5 -null
        while (pcur) {
            // right -->left
            ppre->next = pcur->next; //删除
            pcur->next = pHead.next;
            pHead.next = pcur;

            pcur = ppre->next;
        }

        return pHead.next;
    }