LinkList10

题目描述[原题链接][https://leetcode-cn.com/problems/sort-list/]

在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。

示例 1:

输入: 4->2->1->3
输出: 1->2->3->4

示例 2:

输入: -1->5->3->4->0
输出: -1->0->3->4->5

算法描述

​ 要求时间复杂度为O(n log n)，暴力解决是不行的，如果把值全拿出来，排完序再依次赋值，会有O(n)的空间复杂度，最后采取归并排序解决这个问题。

C++代码

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        ListNode d(0);
        d.next = head;
        auto p = head;
        int length = 0;
        while(p){
            ++length;
            p=p->next;
        }
        for(int size = 1;size<length;size<<=1){
            ListNode* cur = d.next;
            ListNode* tail = &d;
            while(cur){
                ListNode* left = cur;
                ListNode* right = cut(left,size);
                cur = cut(right,size);
                
                tail->next=merge(left,right);
                while(tail->next){
                    tail = tail->next;
                }
            }
        }
        return d.next;
    }
    ListNode* cut(ListNode* head,int n){
        ListNode* p = head;
        while(--n&&p){
            p=p->next;
        }
        if(!p)return nullptr;
        auto next = p->next;
        p->next = nullptr;
        return next;
    }
    ListNode* merge(ListNode* l1,ListNode* l2){
        ListNode d(0);
        auto p =&d;
        while(l1&&l2){
            if(l1->val<l2->val){
                p->next = l1;
                p = l1;
                l1 = l1->next;
            }else {
                p->next = l2;
                p = l2;
                l2 = l2->next;
            }
        }
        p->next = l1?l1:l2;
        return d.next;
    }
};

Java代码

class Solution {
    public ListNode sortList(ListNode head) {
        ListNode d = new ListNode(0);
        d.next = head;
        ListNode p = head;
        int length = 0;
        while(p!=null){
            ++length;
            p=p.next;
        }
        for(int size = 1;size<length;size<<=1){
            ListNode cur = d.next;
            ListNode tail = d;
            while(cur!=null){
                ListNode left = cur;
                ListNode right = cut(left,size);
                cur = cut(right,size);
                
                tail.next = merge(left,right);
                while(tail.next!=null){
                    tail = tail.next;
                }
            }
        }
        return d.next;
    }
    
    ListNode cut(ListNode head,int n){
        ListNode p = head;
        while(--n!=0&&p!=null){
            p=p.next;
        }
        if(p==null)return null;
        ListNode next = p.next;
        p.next = null;
        return next;
    }
    
    ListNode merge(ListNode l1,ListNode l2){
        ListNode d = new ListNode(0);
        ListNode p = d;
        while(l1!=null&&l2!=null){
            if(l1.val<l2.val){
                p.next = l1;
                p = l1;
                l1=l1.next;
            }else {
                p.next = l2;
                p = l2;
                l2 = l2.next;
            }
        }
        p.next =(l1!=null)?l1:l2;
        return d.next;
    }
}