高端行业网站建设百度广告联系方式

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

第一种方法：类似双指针

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

ListNode* partition(ListNode* head, int x) {ListNode* bigpos = nullptr;ListNode* littlepos = nullptr;ListNode* res2 = head;while(head != nullptr){//用两个临时变量记录当前的node和node->nextListNode* tmp1 = head;ListNode* tmp2 = head->next;//如果当前node小于目标值，就要放在little那一部分if(head->val < x){//如果第一次扫到小值部分if(littlepos == nullptr){//直接赋值给littleposlittlepos = 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->nexttmp1->next = littlepos->next;//littlepos->next需要指向当前nodelittlepos->next = tmp1;//如果此时bigpos有值，则需要把bigpos->next指向当前node->next，即tmp2//if(bigpos) 这里不需要判断bigpos//走到这里，littlepos->next与当前node不相同，bigpos肯定有值了bigpos->next = tmp2;}//更新littlepos的位置littlepos = tmp1;}}//大值都在后边，bigpos直接更新elsebigpos = 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;}