题解 | #划分链表#

/**
 * struct ListNode {
 *    int val;
 *    struct ListNode *next;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param head ListNode类 
     * @param x int整型 
     * @return ListNode类
     */
    ListNode* partition(ListNode* head, int x) {
        // write code here
        //思路：小于x的元素翻转到前面 自然大于x元素后面( 1)
        //细节1：原始相对顺序 ->基本操作：链表tail插入
        //细节2：如果小x，并且相对顺序已经正确（在同一个位置删除，和插入）等于不变
        //-->三个指针移动
        //细节3:分割后 head 可能发生变化 ，也可能没有发生变化 需要nedd

         if (nullptr == head || nullptr ==head->next)
         {
             return head;
         }

         ListNode myhead(-1);//基本操作:构造一个固定不变头节点
         myhead.next =head;

        ListNode* ptail = &myhead;
        ListNode* pcur = head;//从第一个元素开始。第一个元素大小不确定.
        ListNode* ppre = &myhead;


        //基本操作：遍历链表  pcur++
          //head-> 5(pcr ) 4 3 2 1 x=2
         while(pcur)
         {
             if (pcur->val >= x)
             {
                  ppre = pcur;
                  pcur = pcur->next;
             }else if (pcur ==ptail->next) //基本操作：else :上上面相反的情况
             {   
                  ptail= ptail->next;
                  ppre = pcur;
                  pcur = pcur->next;
             }else
             {
                 ppre->next = pcur->next;
                 pcur->next = ptail->next;
                 ptail->next = pcur;

                 ptail = pcur;

                 pcur = ppre->next;
             }
         }


        return myhead.next;

    }
};