[C/C++]数据结构 链表OJ题: 链表分割

 
class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
         //带哨兵位
         ListNode* head1,*tail1,*head2,*tail2;
         head1=tail1=(ListNode*)malloc(sizeof(ListNode));
         head2=tail2=(ListNode*)malloc(sizeof(ListNode));
 
         ListNode* cur=pHead;
        //小于x的结点尾插到head1,大于x的结点尾插到head2
         while(cur)
         {
            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;
         }
};