题解 | 链表分割

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
#include <cstdlib>
class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        // write code here
        ListNode* tail1,* tail2,*tail3,*tail4;
        tail1=tail3=(ListNode*)malloc(sizeof(ListNode));
        tail2=tail4=(ListNode*)malloc(sizeof(ListNode));
        tail1->next=tail2->next=nullptr;
        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=tail4->next;
        tail2->next=NULL;
        pHead=tail3->next;
        free(tail3);
        free(tail4);
        return pHead;
    }
};