❣️1.题目
描述 现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。
❣️2.解答
输入参数包括一个指向链表头节点的指针和一个分割值x。函数将链表分为两个部分，一个部分中的节点值小于x，另一个部分中的节点值大于等于x。最终返回分割后的链表头指针。
函数内部定义了4个指针变量head1,tail1,head2,tail2分别表示两个链表的头尾节点。然后对输入的链表进行遍历，如果节点值小于x，则将其插入head1到tail1所表示的链表中；否则将其插入head2到tail2所表示的链表中。最后将两个链表连接起来，形成最终的分割链表。最后释放head1和head2占用的内存。
代码语言：javascript复制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;
}
};
