算法学习 - 链表之归并排序_O(一)空间_O(NlogN)时间_C++

算法学习 - 链表之归并排序_O(1)空间_O(NlogN)时间_C++

归并排序

归并排序我在之前已经讲过了，并且给了在数组的数列的情况下的归并排序方法，而排序的时间复杂度为O(NlogN).想看的话链接如下：
归并排序，快排，冒泡排序

但是这个归并排序有一个缺点：需要O(n)的额外空间。

那么这个缺点在什么情况下会解决呢？就是数列是以链表形式存储的时候！就不需要额外的申请O(n)级别的空间。

那么我们为什么要用归并排序呢？ 不是还有快排，堆排么？都是速度很快的排序。其实在链表中是不适合的！因为在快排的时候，查找标杆是O(1)级别的，但是在链表中只能得到head节点，得到标杆需要O(n)级别的。那么复杂度就上升到(nnlogn)级别的了。

代码实现

所以在链表的情况下需要使用归并排序，复杂度NlogN, 而且不需要申请额外空间。

//
//  main.cpp
//  MergeList
//
//  Created by Alps on 14/12/6.
//  Copyright (c) 2014年 chen. All rights reserved.
//

#include <iostream>
using namespace std;

struct ListNode{
    int val;
    ListNode* next;
    ListNode(int x):val(x),next(NULL){}
};

class Solution{
public:
    ListNode *sortList(ListNode* head){
        if (head == NULL || head->next == NULL) {
            return head;
        }
        
        ListNode* mid = getMid(head);
        ListNode* right = NULL;
        if (mid != NULL) {
            right = mid->next;
            mid->next = NULL;
        }
        head = sortList(head);
        right = sortList(right);
        head = MergeList(head, right);
        return head;
    }
    
    ListNode* getMid(ListNode* node){
        if (node == NULL || node->next == NULL) {
            return node;
        }
        ListNode* l1 = node;
        ListNode* l2 = node->next;
        while (l2 && l2->next) {
            l1 = l1->next;
            l2 = l2->next->next;
        }
        return l1;
    }
    
    ListNode* MergeList(ListNode* left, ListNode* right){
        if (left == NULL) {
            return right;
        }
        if (right == NULL) {
            return left;
        }
        ListNode* temp = NULL;
        if (left->val >= right->val) {
            temp = right->next;
            right->next = left;
            left = right;
            right = temp;
        }
        left->next = MergeList(left->next, right);
        return left;
    }
};

int main(int argc, const char * argv[]) {
    Solution sl;
    ListNode *head = new ListNode(4);
    head->next = new ListNode(2);
    head->next->next = new ListNode(1);
    head->next->next->next = new ListNode(3);
    sl.sortList(head);
    return 0;
}