题解 | #链表分割#

/* struct ListNode { int val; struct ListNode next; ListNode(int x) : val(x), next(NULL) {} };/ class Partition { public: ListNode* partition(ListNode* pHead, int x) { //1创建指针4个，和链表遍历指针cur ListNode* bigTail,bigHead,smallTail,smallHead; bigHead=bigTail=(ListNode)malloc(sizeof(ListNode)); smallHead=smallTail=(ListNode)malloc(sizeof(ListNode)); ListNode cur=pHead; //2.遍历链表,处理边界情况 if(cur==NULL) return NULL; else if(cur->next==NULL) return pHead; while(cur) { if(cur->val>=x) { bigTail->next=cur; bigTail=cur; } else { smallTail->next=cur; smallTail=cur; } cur=cur->next; } //3.连接链表，处理可能成环情况 smallTail->next=bigHead->next; bigTail->next=NULL; ListNode* head=smallHead->next; free(bigHead); free(smallHead); return head; } };