148. Sort List

problem description

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

Example 1:

Input: 4->2->1->3
Output: 1->2->3->4

Example 2:

Input: -1->5->3->4->0
Output: -1->0->3->4->5

algorithm thought

需要使用nlgn时间复杂度排序链表，显然，这里用归并排序会很好。还需要常数空间复杂度。既然是常数时间，那就不能使用递归解决，但是我还是觉得递归解决舒服很多，并且很快很清晰，所以我是使用递归解决的。

归并排序有两部分，一部分是对两半个链表排序，然后就排好序的链表合并，链表合并问题，我们之前的问题也讨论过了

code

/**
 * 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) {
        if(head==NULL||head->next==NULL)
            return head;
        else if(head->next->next==NULL){
            ListNode* tmp=head->next;
            head->next=NULL;
            return merge(head,tmp);
        }else{
            ListNode* mid=head,*fast=head;
            while(fast->next&&fast->next->next){
                fast=fast->next->next;
                mid=mid->next;
            }
            cout<<mid->val<<' ';
            fast=mid->next;
            mid->next=NULL;
            return merge(sortList(head),sortList(fast));
        }
        return NULL;
    }
    ListNode* merge(ListNode* l1,ListNode* l2){
        if(l1==NULL)
            return l2;
        if(l2==NULL)
            return l1;
        if(l1->val<l2->val){
            l1->next=merge(l1->next,l2);
            return l1;
        }else{
            l2->next=merge(l1,l2->next);
            return l2;
        }
        return NULL;
    }
};

algorithm analysis

就想thought中说的那样，时间复杂度肯定是O(nlgn)，对于归并排序时间复杂度的详细分析，可以看看主定理。但是空间复杂度还是没到常数，空间复杂度也是O(nlgn)