题解 | #链表分割#

/* struct ListNode { int val; struct ListNode next; ListNode(int x) : val(x), next(NULL) {} };/ class Partition { public: ListNode* partition(ListNode* pHead, int x) { //创建哨兵位 方便尾插 ListNode* less_head, *greater_head, less_tail, greater_tail; less_head = less_tail = (ListNode)malloc(sizeof(ListNode)); greater_head = greater_tail = (ListNode)malloc(sizeof(ListNode)); less_tail->next = NULL; greater_tail->next = NULL;

    ListNode* cur = pHead;
    while(cur)
    {
        if(cur->val < x)
        {
            less_tail->next = cur;
            less_tail = less_tail->next;
        }
        else
        {
            greater_tail->next = cur;
            greater_tail = greater_tail->next;
        }
        cur = cur->next;
    }
    //链接两个链表
    less_tail->next = greater_head->next;
    //关键点 防止成环
    greater_tail->next = NULL;
    //给头节点
    pHead = less_head->next;
    //释放空间
    free(less_head);
    free(greater_head);
    return pHead;
}

};