题解 | #链表分割#

struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        // write code here
        struct ListNode*head1,*head2,*tail1,*tail2;
         head1=tail1=(struct ListNode*)malloc(sizeof(struct ListNode));
         head2=tail2=(struct ListNode*)malloc(sizeof(struct ListNode));
        tail1->next=NULL;
        tail2->next=NULL;
        struct ListNode* cur=pHead;
        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;
    }
# };