链表的分割

链表的分割

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能，轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/partition-list-lcci/submissions/496780619/

给你一个链表的头节点?head?和一个特定值?x?，请你对链表进行分隔，使得所有?小于?x?的节点都出现在?大于或等于?x?的节点之前。

你不需要?保留?每个分区中各节点的初始相对位置。

思路：
弄两个链表然后合到一块。

易错点：‘

结束时greaterTail是和cur（lessTail）连着的，构成了一个环，所以应置空。’

不置空会报错

代码：

struct ListNode* partition(struct ListNode* head, int x){
       struct ListNode*lessHead,*lessTail,*greaterHead,*greaterTail;
       lessHead=lessTail=(struct ListNode*)malloc(sizeof(struct ListNode));
       lessTail->next=NULL;
       greaterHead=greaterTail=(struct ListNode*)malloc(sizeof(struct ListNode));
       greaterTail->next=NULL;
       struct ListNode*cur=head;
       while(cur){
           if(cur->val<x){
               lessTail->next=cur;
               lessTail=cur;
           }
           else{
               greaterTail->next=cur;
               greaterTail=cur;
           }
           cur=cur->next;
       }
       lessTail->next=greaterHead->next;
       //greaterTail->next=NULL;
       struct ListNode*newHead=lessHead->next;
       free(lessHead);
       free(greaterHead);
       return newHead;
}