首页 > 代码库 > [LeetCode] Sort List

[LeetCode] Sort List

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

一谈到时间复杂度O(nlogn),立即联想到以下3种排序方法:

1.归并排序(基于分治):时间复杂度O(nlogn),归并排序的最好、平均、最坏时间复杂度没有差别,空间复杂度是O(n),稳定的排序算法。

                                                                                                                                   用链表实现,则空间复杂度可为O(1)

2.堆排序                    :时间复杂度O(nlogn),堆排序的最好、平均、最坏时间复杂度没有差别,空间复杂度是O(1),不稳定的排序算法。

3.快速排序(基于分治):不稳定的排序算法。

                                   时间复杂度最好为O(nlogn), //对应完全二叉树

                                                 最坏为O(n^2),  //数据元素已全部有序反而此排序算法不利,对应单分支二叉树

                                                 期望为O(nlogn)。

                                   空间复杂度最好为O(logn),

                                                  最坏为O(n), 

                                                  期望为O(logn)。 

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

 

class Solution {
private:
ListNode *merge(ListNode* l1, ListNode* l2, ListNode* h){ //h是本分组的前一个指针,返回tail本分组的末尾指针
   
    ListNode **ref;  //使用指针的指针(注:在被调用的函数中,要改变指针指向的值,用指针;要改变指针,用指针的指针)
    while(l1||l2){
        if(!l1){
         ref = &l2;
        }
        else if(!l2){
         ref = &l1;
        }
        else if(l1->val<l2->val){
         ref = &l1;
        }
        else {
          ref = &l2;
        }
        h->next = *ref;
        *ref = (*ref)->next;//这就是使用指针的指针的本意,此处改变的是l1或l2的指向,使得if中的代码简化很多。
        h=h->next;
    }
    return h;
}

ListNode* split(ListNode* h, int len){//参数是本分组的头指针h和本分组的最大可能长度len,作用:使本分组的末尾节点的next是NULL,并返回下一分组的头指针
    for(int i=1;i<len&&h!=NULL;i++){
        h=h->next;
    }
    if(!h) return NULL;
    ListNode* t=h->next;
    h->next=NULL;
    return t;
}
public:
ListNode *sortList(ListNode *head) {
    ListNode n(0);                  //不是指针可以不用new
    n.next=head;
    int listlen=0;
    while(head){listlen++;head=head->next;}
    for(int len=1;len<listlen;len*=2){
        ListNode* t=n.next,*l1,*l2;
        ListNode* h=&n;
        while(t!=NULL){
            l1=t;            //分配l1分组的头指针
            l2=split(t,len);//使l1分组的末尾指向NULL,返回l2分组的头指针
            t=split(l2,len);//使l2分组的末尾指向NULL,返回下个分组的头指针
            
            ListNode* tail=merge(l1,l2,h);//h是本分组的前一个指针,返回tail本分组的末尾指针
            tail->next=t;
            h=tail;
        }
    }
    return n.next;
}
};