题解 | #划分链表#

搜索 微信公共号：offer 多多


class Solution3 {
public:
    /**
     * 
     * @param head ListNode类 
     * @param x int整型 
     * @return ListNode类
     */
    ListNode* partition(ListNode* phead, int x) {
        // write code here

        //01 
        if (nullptr == phead || nullptr == phead->next)
        {
            return phead;
        }

        //02 返回结果 如果head小于k 返回结果就是head，大于则不是，不确定因此 why
        ListNode myhead(-1);
        myhead.next = phead;
        ListNode* ptail = &myhead;

       //03 
       ListNode* pcur =phead; // 第一个节点大小不确定，无法默认就是分割好的（反转，奇偶 插入排序）
       ListNode* ppre =&myhead;

       while(pcur)
       {

         if(pcur->val >= x)
         {   ////case 1 移动
             ppre = pcur ;
             pcur = pcur->next;//i++
         }else if (ptail->next == pcur)
         {  //bug1  ptail->next = pcur
             //case 2移动
             ptail = ptail->next;//move
             ppre = pcur ;
             pcur = pcur->next;//i++

         }else
         {
            //case3 反转
            ppre->next = pcur->next;
            pcur->next =ptail->next;
            ptail->next = pcur;
            ptail = pcur;//move

            pcur = ppre->next;


         }

       }
        return myhead.next;
    }

};

//g++ -std=c++11 tag_list_01.cpp
int main()
{   
    //vector<int> test={1,2,3,4,5};
    vector<int> test={5,4,3,2,1};
    ListNode* pInput= createList(test);
    cout<< "input: " ;
    show(pInput);

   Solution3 s3;
   ListNode* pOnput=s3.partition(pInput,3);
    cout<< "outut: " ;
    show(pOnput);

    return 0; 
}