本文共 1863 字，大约阅读时间需要 6 分钟。

/** * Definition for singly-linked list. * struct ListNode { *     int val; *     ListNode *next; *     ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {
   public:    ListNode* partition(ListNode* head, int x) {
           queue
   
     LowData;        queue
    
      HightData;        ListNode* cur = head;        while(cur!=nullptr){
               if(cur->val
     
      next;        }        ListNode* out = new ListNode(0);        cur = out;        while(!LowData.empty()){
               cur->next = LowData.front();            cur = cur->next;            LowData.pop();        }        while(!HightData.empty()){
               cur->next = HightData.front();            cur=cur->next;            HightData.pop();        }        cur->next = nullptr;        return out->next;    }};
     
    
   

方法二：引入了n个常量空间，因此想直接在链表上进行调整。需要引入双指针，先找到第一个不满足条件的值，再遍历后面寻找其他不满足条件的值插入。需要注意的是边界条件的情况以及删除插入过程的现成保护：

/** * Definition for singly-linked list. * struct ListNode { *     int val; *     ListNode *next; *     ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {
   public:    ListNode* partition(ListNode* head, int x) {
           if(head==nullptr)            return nullptr;;        ListNode* new_head = new ListNode(0);        new_head->next = head;        ListNode* lp=new_head;        ListNode* rp=head;        while(rp->val
   
    next;            lp=lp->next;            if(rp==nullptr)                return head;        }        ListNode* mid = lp;        while(rp!=nullptr){
               if(rp->val
    
     next = rp->next;                rp = rp->next;                temp->next = mid->next;                mid->next = temp;                mid = temp;            }            else{
               rp=rp->next;            lp=lp->next;            }        }        return new_head->next;    }};
    
   

转载地址：http://bvyci.baihongyu.com/