牛客—CM11 链表分割

大家好，欢迎来到IT知识分享网。

❣️1.题目

❣️2.解答

输入参数包括一个指向链表头节点的指针和一个分割值x。函数将链表分为两个部分，一个部分中的节点值小于x，另一个部分中的节点值大于等于x。最终返回分割后的链表头指针。

函数内部定义了4个指针变量head1,tail1,head2,tail2分别表示两个链表的头尾节点。然后对输入的链表进行遍历，如果节点值小于x，则将其插入head1到tail1所表示的链表中；否则将其插入head2到tail2所表示的链表中。最后将两个链表连接起来，形成最终的分割链表。最后释放head1和head2占用的内存。

class Partition { public: ListNode*partition(ListNode*pHead,int x){ struct ListNode*head1,*tail1,*head2,*tail2; head1 = tail1= (struct ListNode*)malloc(sizeof(struct ListNode)); head2 = tail2= (struct ListNode*)malloc(sizeof(struct ListNode)); struct ListNode* cur =pHead; while(cur) { //<x尾插到tail1 //>=x尾插到tai12 if(cur->val <x) { tail1->next =cur; tail1=tail1->next; } else { tail2->next =cur; tail2=tail2->next; } cur=cur->next; } tail1->next = head2->next; tail2->next = NULL; pHead =head1->next; free(head1); free(head2); return pHead; } };