题目链接：86. 分隔链表 - 力扣（LeetCode）

第一种方法：类似双指针

自己想的，不知道读者是否能看懂，参考注释

ListNode* partition(ListNode* head, int x) {
        ListNode* bigpos = nullptr;
        ListNode* littlepos = nullptr;
        ListNode* res2 = head;
        while(head != nullptr)
        {
            //用两个临时变量记录当前的node和node->next
            ListNode* tmp1 = head;
            ListNode* tmp2 = head->next;
            //如果当前node小于目标值，就要放在little那一部分
            if(head->val < x)
            {
                //如果第一次扫到小值部分
                if(littlepos == nullptr)
                {
                    //直接赋值给littlepos
                    littlepos = tmp1;
                    //如果bigpos已经有值，那么需要把第一个littlepos放在链表第一个
                    //bigpos->next指向当前node的下一个位置，即tmp2
                    //而且要记得更新链表头res2,需要返回
                    if(bigpos)
                    {
                        bigpos->next = tmp2;
                        tmp1->next = res2;
                        res2 = tmp1;
                    }
                }
                else//不是第一次扫到小值
                {
                    //如果是littlepos->next = tmp1,说明是连续扫到的小值，并且目前链表只有小值
                    //无须下列步骤，直接可以更新littlepos位置
                    if(littlepos->next != tmp1)
                    {
                        //把当前node->next指向littlepos->next
                        tmp1->next = littlepos->next;
                        //littlepos->next需要指向当前node
                        littlepos->next = tmp1;
                        //如果此时bigpos有值，则需要把bigpos->next指向当前node->next，即tmp2
                        //if(bigpos) 这里不需要判断bigpos
                        //走到这里，littlepos->next与当前node不相同，bigpos肯定有值了
                        bigpos->next = tmp2;
                    }
                    //更新littlepos的位置
                    littlepos = tmp1;
                }
            }
            //大值都在后边，bigpos直接更新
            else
                bigpos = tmp1;
            head = tmp2;//更新head的值
        }
        return res2;
    }

第二种方法：双指针

创建两个链表头，把以target为目标的分到两个链表中

ListNode* partition(ListNode* head, int x) {
        ListNode* littleList = new ListNode(-1);
        ListNode* bigList = new ListNode(-1);
        ListNode* res = littleList;
        ListNode* bigFront = bigList;
        int i = 0;
        while(head)
        {
            if(head->val < x)
            {
                littleList->next = head;
                littleList = littleList->next;
                head = head->next;
                littleList->next = nullptr;
            }
            else
            {
                bigList->next = head;
                head = head->next;
                bigList = bigList->next;
                bigList->next = nullptr;
            }
            //这里非常容易出问题，看着类同的代码，如果拿出来就会出错
            //因为这里是指针类型，littleList和bigList均为当前的head
            //上述结束之后，如果放在这里更新head，head->next已经为空了
            //head = head->next;
        }
        littleList->next = bigFront->next;
        return res->next;
    }