96. 链表划分链表拆分

 ListNode * partition(ListNode * head, int x) {
        
        if(head==NULL)    //如果是空链表，返回空
            return NULL;
            
        ListNode *small=new ListNode(0);         //小列表的假表头
        //这个假表头应该是实体，因为操作的是它的next，如果本身就是空的，那么操作next就会出错。
        ListNode *small_back;   //最后一节点
        ListNode *big=new ListNode(0);           //大列表的假表头
        ListNode *big_back;     //最后一个节点
        
        ListNode *tmp=NULL;
        
        while(head)         
        {
            tmp=head;
            
            head=head->next;   //HEAD被tmp接管,head后移
            
            tmp->next=NULL;
            
            if(tmp->val<x)
            {
                if(!small->next)  //还是空的
                {
                    small->next=tmp;   //第一个接上来
                    small_back=small->next;   //后移
                }
                else
                {
                    small_back->next=tmp;
                    small_back=small_back->next;

                }
            }
            else
            {
                if(!big->next)
                {
                    big->next=tmp;
                    big_back=big->next;
                }
                else
                {
                    big_back->next=tmp;
                    big_back=big_back->next;

                }
            }
            
        }
        if(!small->next)   return big->next;    
//这里的判断一定要写next,新建假表头一切以假表头为准，一开始忘记写next怎么也通不过，气死！
        if(!big->next)    return small->next;
        small_back->next=big->next;
        return small->next;
        
            // write your code here
    }