题解 | #链表分割#

主要思想:把大于x的值放到一个链表，小于x的值放到一个链表，然后再把两个链表合起来。

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class Partition {
  public:
    ListNode* partition(ListNode* pHead, int x) {
        struct ListNode* lesshead, *lesstail, *greathead, *greattail;
        lesshead = lesstail = (struct ListNode*)malloc(sizeof(struct ListNode));
        lesshead->next = NULL;
        greathead = greattail = (struct ListNode*)malloc(sizeof(struct ListNode));
        greathead->next = NULL;
        ListNode* cur = pHead;
        while (cur) {
            if (cur->val < x) {
                lesstail->next = cur;
                lesstail = cur;
            } else {
                greattail->next = cur;
                greattail = cur;
            }
            cur = cur->next;
        }
        // cout<<"%d"<<lesshead->next->val<<endl;
        
        lesstail->next = greathead->next;
        greattail->next = NULL;

struct ListNode* newhead = lesshead->next;//要后创建，不然lesshead->next为空的结果就不能通过
        free(lesshead);
        free(greathead);

        return newhead;
    }
};