题解 | 链表分割

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class Partition {
  public:
    typedef struct ListNode LTN;
    ListNode* partition(ListNode* pHead, int x) {
        //创建大小链表
        //小链表
        ListNode* lessHead = NULL, *lessTail = NULL;
        lessHead = lessTail = (LTN*)malloc(sizeof(LTN));
        //大链表
        ListNode* greaterHead = NULL, *greaterTail = NULL;
        greaterHead = greaterTail = (LTN*)malloc(sizeof(LTN));
        LTN* pcur = pHead;
//遍历原链表，按照大小插入不同链表
        while (pcur != NULL) {
            if (pcur->val < x) { //插入小链表
                lessTail->next = pcur;
                lessTail = lessTail->next;
            } else { //插入大链表
                greaterTail->next = pcur;
                greaterTail = greaterTail->next;
            }
            //向后遍历
            pcur = pcur->next;
        }
//把大链表最后一个结点的next置空
        greaterTail->next = NULL;
//拼接大小链表
        lessTail->next = greaterHead->next;

//保存新链表的第一个结点
        LTN* ret = lessHead->next;
//释放空间
        free(lessHead);
        free(greaterHead);
//返回新链表
        return ret;

    }
};