题解 | #链表分割#

/*
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* cur = phead;
        struct ListNode* list1,*tail1,*list2,*tail2;

        //哨兵位
       list1 = tail1= (struct ListNode*)malloc(sizeof(struct ListNode));
       list2 = tail2= (struct ListNode*)malloc(sizeof(struct ListNode));

       while(cur)
       {
            if(cur->val < x)    //小于x
            {
                tail1->next = cur;
                tail1 = tail1->next;
            }
            else    //大于等于x
            {
                tail2->next = cur;
                tail2 = tail2->next;
            }
            cur = cur->next;
       }
       tail1->next = list2->next;   //链接两条链表
       tail2->next = NULL;  //尾部置NULL
       
       phead = list1->next;
       free(list1);
       free(list2);
       return phead;
    }
};