C++ 解法, 执行用时: 2ms, 内存消耗: 332KB, 提交时间: 2021-03-20

/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 * };
 */
class Solution {
public:
    /**
     * @param head ListNode类      * @param x int整型      * @return ListNode类
     */
    ListNode* partition(ListNode* head, int x) {
        // write code here
        ListNode* LH=NULL;
        ListNode* LT=NULL;
        ListNode* RH=NULL;
        ListNode* RT=NULL;
        ListNode* a=head;
        while (a!=nullptr)
        {
            ListNode* next=a->next;
            a->next=NULL;
            if (a->val<x)
            {
                if (LH==nullptr)
                {
                    LH=a;
                    LT=a;
                }
                else
                {
                    LT->next=a;
                    LT=a;
                }
            }
            else
            {
                if (!RH)
                {
                    RH=a;
                    RT=a;
                }
                else
                {
                    RT->next=a;
                    RT=a;
                }
            }
            a=next;
        }
        if (LH)
        {
            LT ->next= (RH==NULL)?NULL:RH;
            return LH;
        }
        else
            return RH;
    }
};

C++ 解法, 执行用时: 2ms, 内存消耗: 340KB, 提交时间: 2021-05-06

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param head ListNode类 
     * @param x int整型 
     * @return ListNode类
     */
    ListNode* partition(ListNode* head, int x) {
        if(head == NULL || head->next == NULL) return head;
        
        ListNode* dummy = new ListNode(-1);
        dummy->next = head;
        
        ListNode* p = head;
        ListNode* low = dummy;
        ListNode* prev = dummy;
        
        while(p)
        {
            if(p->val>=x)
            {
                prev = p;
                p = p->next;
            }
            else
            {
                if (p == low->next) {
                    prev = p;
                    p = p->next;
                    low = low->next;
                }
                else {
                    prev->next = p->next;
                    p->next = low->next;
                    low->next = p;
                    low = p;
                    p = prev->next;
                }
            }
        }
        
        head = dummy->next;
        delete dummy;
        
        return head;
    }
};

C++ 解法, 执行用时: 2ms, 内存消耗: 340KB, 提交时间: 2021-01-24

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param head ListNode类 
     * @param x int整型 
     * @return ListNode类
     */
    ListNode* partition(ListNode* head, int x) {
        // write code here
        if(head == NULL)
            return NULL;
        ListNode* p = head;
        while(p!=NULL)
        {
            while(p!=NULL && p->val<x)
            {
                p=p->next;
            }
            if(p==NULL)
            {
                return head;
            }
            ListNode* q = p;
            while(q !=NULL && q->val>=x )
            {
                q=q->next;
            }
            if(q==NULL)
            {
                return head;
            }
            int pre = p->val;
            ListNode* cur = p;
            cur->val = q->val;
            cur=cur->next;
            while(cur!=NULL)
            {
                int tmp = cur->val;
                cur->val=pre;
                pre = tmp;
                if(cur == q)
                    break;
                cur=cur->next;
            }
            p=p->next;
        }
        return head;
    }
};

C++ 解法, 执行用时: 2ms, 内存消耗: 348KB, 提交时间: 2021-05-06

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param head ListNode类 
     * @param x int整型 
     * @return ListNode类
     */
    ListNode* partition(ListNode* head, int x) {
        // write code here
        ListNode* list1 = new ListNode(-1), *p1 = list1;
        ListNode* list2 = new ListNode(-1), *p2 = list2;
        ListNode* p = head;
        while(p!=nullptr){
            if(p->val<x){
                p1->next = new ListNode(p->val);
                p1 = p1->next;
            }else{
                p2->next = new ListNode(p->val);
                p2 = p2->next;
            }
            p = p->next;
        }
        p1->next = list2->next;
        return list1->next;
    }
};

C++ 解法, 执行用时: 2ms, 内存消耗: 348KB, 提交时间: 2020-12-16

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param head ListNode类 
     * @param x int整型 
     * @return ListNode类
     */
    ListNode* partition(ListNode* head, int x) {
        // write code here
        if(head == nullptr) return nullptr;
        ListNode *head1 = new ListNode(0);
        ListNode *head2 = new ListNode(0);
        ListNode *p1 = head1, *p2 = head2, *p = head;
        while(p) {
            if(p->val < x) {
                p1->next = p;
                p1 = p1->next;
            } else {
                p2->next = p;
                p2 = p2->next;
            }
            p = p->next;
        }
        p1->next = head2->next;
        p2->next = nullptr;
        return head1->next;
    }
};