148.md

Sort List

题目

Sort a linked list in O(n log n) time using constant space complexity.

限制空间为常量空间内将一个链表排序，所以将链表拷贝到一个数组调用sort是不可能的。

思路

   //运行蜜汁慢 不知道为啥    在链表上实现快排。

   对于一个链表，头指针为head，长度为len，设置接口partition(ListNode* head,int len){}将head排序，partition是一个递归函数。

   partition的实现就是快排的核心，但是写法最好是遍历的写法，而不是两个指针操控的写法。

   设置第一个元素为key=head->val，设置一个指针first_big指向第一个比key大的元素，初始化first_big指向第二个结点的位置，第二个结点有可能为空。    first_big为空表示没有比key小的元素值。设置一个前置指针front指向first_big的前1位置。

   遍历后面的每一个元素(即循环len-1次)，如果该元素比key小则将该元素的值与first_big的值交换。更新first_big = first_big->next.    这一步的操作的意义就是将小的元素放到前面。

   遍历完后检测first_big是否为nullptr，如果指向空表示没有大于key的元素则

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        int len = 0;
        ListNode* tmp=head;
        while(tmp){
            len++;
            tmp = tmp->next;
        }
        if(head) partition(head,len);
        return head;
    }
    
    void partition(ListNode* head,int count){
        int key = head->val; //设置第一个元素为关键值
        if(count==0) return;
        int front_count = 0;//统计比key小的元素个数
        int back_count =0;  //统计比key大的元素个数
        ListNode* head_copy = head;//保留头指针
        //指向第一个大于key的值的位置
        ListNode* front_first_bigger=nullptr;
        head = head->next;
        ListNode* first_bigger=head;
        while(--count){
            //比key小则交换比key大的第一个值和当前值。
            if(head->val<key){
                swap(head->val,first_bigger->val);
                //更新前置指针，指向first_bigger的前一位置
                front_first_bigger = first_bigger;
                first_bigger = first_bigger->next;
                front_count++;
            }else{
                back_count++;
            }
            head = head->next;
        }
        //交换key和最后一个比key小的元素(在处理一边后的链表上的序列位置的最后一个)
        if(front_first_bigger) swap(head_copy->val,front_first_bigger->val);
        //处理前半部分
        if(head_copy) partition(head_copy,front_count);
        //处理后半部分
        if(first_bigger) partition(first_bigger,back_count);
    }
    
};