题解 | #链表分割#

/*
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
        /*思路：小于的跟着一个哨兵头，非小于的跟着另一个哨兵头，第一个哨兵头的结尾连着另外一个哨兵头的next，*/
        ListNode* guard = (ListNode*)malloc(sizeof(ListNode));/*两个哨兵头，分别代表小于x和不小于x的哨兵头*/
        ListNode* guard2 = (ListNode*)malloc(sizeof(ListNode));
        guard->next = NULL;
        guard2->next = NULL;
        ListNode* guard_cur = guard;/*统计小于x的节点*/
        ListNode* guard_cur2 = guard2;/*统计不小于x的节点*/
        ListNode* cur = pHead;/*统计所有节点*/
        while(cur)
        {
            if(cur->val < x)
            {
                guard_cur->next = cur;
                guard_cur = guard_cur->next;
            }
            else
            {
                guard_cur2->next = cur;
                guard_cur2 = guard_cur2->next;
            }
            cur = cur->next;
        }
        guard_cur->next = NULL;
        guard_cur2->next = NULL;
        guard_cur->next = guard2->next;
        pHead = guard->next;
        free(guard);
        free(guard2);
        return pHead;
    }
};