题目描述

思路

先想到的一个方法是快慢指针扫描小于x的结点，然后把这些节点插入到慢指针后面去，但是写着写着好像发现这个题也可以用递归来写，后面的若干个结点的子表和整个问题的性质是一样的。
普通方法的代码如下：

//只是大致是这样，这个代码还有一些用例跑不过
class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        if(head == nullptr ){
            return head;
        }
        if(head -> next == nullptr && head -> val < x){
            return head;
        }
        ListNode* Dummy = new ListNode(0,head);
        ListNode* slow = Dummy;
        ListNode* fast = Dummy;

        if(head -> val < x){
            slow = head ;
            fast = slow;
        }else{
            slow = Dummy;
            fast = Dummy;
        }
        while(slow != nullptr && fast-> next != nullptr){
            if(fast-> next->  val < x ){
                ListNode* tmp = fast -> next;
                fast -> next = tmp -> next;
                tmp -> next = slow -> next;
                slow -> next = tmp;
                slow = tmp;
                continue;
            }
            fast = fast -> next;
        }
        return Dummy -> next;
    }
};

递归算法的代码如下：

class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        //基本问题
        if(head == nullptr || head -> next == nullptr){
            return head;
        }
        ListNode* Dummy = new ListNode(0, head);
        ListNode* cur;
        head-> next = partition(head -> next, x);
        if(head-> val >= x){
            Dummy-> next = head -> next;
            cur = Dummy;
            while(cur -> next != nullptr && cur -> next -> val < x){
                cur = cur -> next;
            }
            head -> next = cur -> next;
            cur ->next = head;
            return Dummy-> next;
        }
        return head;
    }
};

一眼就可以看出递归算法的优势，逻辑简单，可读性强，不易出错。