高端行业网站建设百度广告联系方式
题目链接: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;}