【Sorting】【Linked List】Sort List

2014-07-20

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

##归并排序 ###思路

使用归并排序，不仅好写，而且似乎对极端情况比较鲁棒一些，顺利过了。
需要注意的是要将链表断开，不断最后会得到一个循环链表，然后收获一枚TLE。

###代码

ListNode* sortList(ListNode* head){
    if(head == NULL || head->next == NULL)
        return head;
    ListNode* walker = head;
    ListNode* runner = head;
    while(runner->next!=NULL && runner->next->next!=NULL){
        walker = walker->next;
        runner = runner->next->next;
    }
    ListNode* head1 = head;
    ListNode* head2 = walker->next;
    walker->next = NULL;//非常重要，将链表断开，一分为二
    
    head1 = sortList(head1);
    head2 = sortList(head2);
    return mergeTwoLists(head1, head2);
}

ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
    if(l1 == NULL)
        return l2;
    else if(l2 == NULL)
        return l1;
        
    ListNode *ResHead, *ResTail;
    ListNode *l1Head = l1;
    ListNode *l2Head = l2; 
    if(l1Head->val < l2Head->val){
        ResHead = l1Head;
        ResTail = l1Head;
        l1Head = l1Head->next;
    }else{
        ResHead = l2Head;
        ResTail = l2Head;
        l2Head = l2Head->next;
    }
    
    //while(l1Head->next != NULL && l2Head->next != NULL)
    while(l1Head != NULL && l2Head != NULL){
        if(l1Head->val < l2Head->val){
            ResTail->next = l1Head;
            ResTail = l1Head;
            l1Head = l1Head->next;
        }else{
            ResTail->next = l2Head;
            ResTail = l2Head;
            l2Head = l2Head->next;
        }
    }
    if(l1Head != NULL){
        ResTail->next = l1Head;
    }else if(l2Head != NULL){
        ResTail->next = l2Head;
    }
    
    return ResHead;
}

##快速排序 ###思路

在partition时，我们用最后的节点作为pivot。当我们扫描链表时，如果节点值大于pivot，将节点移到尾部之后；如果节点小于，保持不变。
在qsortList主体，注意pivot左右为空的细节，并且记得把两个链表拼接起来。
做了一些优化，还是TLE在只由1、2、3组成的3w序列上。因为quickSort算法的最坏情况是O(n*n)，所以如果做LeetCode上的Sort List这道题目，会遇上最坏情况超时。随机选pivot比较麻烦一点，如果有好心人告诉我这样可否避免就好了。
QuickSort on Singly Linked List QuickSort on Doubly Linked List

###代码

ListNode* sortList(ListNode* head){
    ListNode* tail = getTail(head);
    return qsortList(head, tail);
}

ListNode* getTail(ListNode* head){
    ListNode* tail = head;
    if(tail == NULL) return tail;//在任何tail->next之前都要三思
    while(tail->next != NULL){
        tail = tail-> next;
    }
    return tail;
}

ListNode* qsortList(ListNode* &head, ListNode* &tail){//以(ListNode* head)的形式调用就是杯具
    if(head == NULL || head->next == NULL)
        return head;
    ListNode* prepivot = NULL;
    ListNode* pivot = NULL;
    partition(head, prepivot, pivot, tail);
    
    if(head != NULL){
        qsortList(head, prepivot);//在partition中保留prepivot的值，不然会超时
        prepivot->next = pivot;
    }else{
        head = pivot;//如果pivot前面没有元素，head会被置为NULL
    }
    
    if(pivot->next != NULL){
        qsortList(pivot->next, tail);
    }
    return head;
}

void partition(ListNode* &head, ListNode* &pre, ListNode* &pivot,ListNode* &tail){
    pivot = tail;
    ListNode* dummy = new ListNode(0);
    dummy->next = head;
    pre = dummy;
    ListNode* tar = head;
    while(tar != pivot){
        if(tar->val > pivot->val){
            pre->next = tar->next;//重要
            tar->next = NULL;
            tail->next = tar;
            tail = tar;
            tar = pre->next;
        }else{
            pre = tar;
            tar = tar->next;
        }
    }
    pre->next = NULL;//重要
    head = dummy->next;
}

【Sorting】【Linked List】Sort List

Tech

Life