LeetCode Hot100 排序链表

给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

示例 1：

输入：head = [4,2,1,3]
输出：[1,2,3,4]

示例 2：

输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]

示例 3：

输入：head = []
输出：[]

归并排序

思路

        题目要求O(nlogn)时间复杂度和O(1)空间复杂度，使用归并排序而非是快速排序，归并排序比快排稳定。把链表分割成节点，再合并

代码 

class Solution {
public:
    ListNode* merge(ListNode* list1, ListNode* list2)
    {
        ListNode* mergelist = new ListNode(0); 
        ListNode* node = mergelist;
        while(list1 != nullptr && list2 != nullptr)
        {
            if(list1->val > list2->val)
            {
                node->next = list2;
                list2 = list2->next;
            }
            else
            {
                node->next = list1;
                list1 = list1->next;
            }
            node = node->next;
        }
        if(list1 != nullptr)
            node->next = list1;
        else if(list2 != nullptr)
            node->next = list2;
        return mergelist->next;
    }
 
    ListNode* sortList(ListNode* head) {     
        if(head == nullptr || head->next == nullptr)
            return head;
        int listlen = 0;
        ListNode* res = new ListNode(0, head);
        while(head != nullptr)
        {
            head = head->next;
            ++listlen;
        }
        for(int i=1; i<listlen; i*=2)
        {
            ListNode* tmp = res->next;
            ListNode* tail = res;
            while(tmp != nullptr)
            {
                ListNode* left = tmp;
                for(int j=1; j<i && tmp->next!=nullptr; ++j)
                    tmp = tmp->next;
                ListNode* right = tmp->next;
                tmp->next = nullptr;
                tmp = right;
                for(int j=1; j<i && tmp!=nullptr && tmp->next!=nullptr; ++j)
                    tmp = tmp->next;
                ListNode* next = nullptr;
                if(tmp != nullptr)
                {
                    next = tmp->next;
                    tmp->next = nullptr;
                }
                tail->next = merge(left, right);
                while(tail->next != nullptr)
                    tail = tail->next;
                tmp = next;
            }
        }
        ListNode* secondhead = res->next;
        delete res;
        return secondhead;
    }
};