题解 | #链表分割#

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        ListNode* bigGuard,*smallGuard,*bigTail,*smallTail;
        bigGuard=bigTail=(ListNode*)malloc(sizeof(struct ListNode));
        smallGuard=smallTail=(ListNode*)malloc(sizeof(struct ListNode));
        bigTail->next=smallTail->next=NULL;
        ListNode* cur=pHead;
        while(cur)
        {
            if(cur->val<x)
            {
                smallTail->next=cur;
                smallTail=smallTail->next;
            }
            else
            {
                bigTail->next=cur;
                bigTail=bigTail->next;
            }
            cur=cur->next;
        }
        bigTail->next=NULL;//需要把大数尾的next置空，否则可能出现死循环
        smallTail->next=bigGuard->next;
        pHead=smallGuard->next;
        free(smallGuard);
        free(bigGuard);
        return pHead;
    }
};