题目介绍：
题目链接：链表分割_牛客题霸_牛客网 (nowcoder.com)?
我们的思想是创建两个带头的链表l1和l2，遍历题目中所给的链表中各个节点的val将小于x的放入l1中，大于x的放入l2中，然后让l1的尾部指向l2的首部，返回l1的头指针。
图解如下：
?代码如下：
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};*/
class Partition {
public:
ListNode* partition(ListNode* pHead, int x) {
struct ListNode* l1=(struct ListNode* )malloc(sizeof(struct ListNode));
struct ListNode* l2=(struct ListNode* )malloc(sizeof(struct ListNode));
struct ListNode* cur=pHead;
struct ListNode* head1=l1;
struct ListNode* head2=l2;
if(cur==NULL)
return NULL;
while(cur)
{
if(cur->val<x)
{
l1->next=cur;
l1=l1->next;
}
else
{
l2->next=cur;
l2=l2->next;
}
cur=cur->next;
}
l1->next=head2->next;
l2->next=NULL;
return head1->next;
}
};
