排序链表---归并--链表OJ

https://leetcode.cn/problems/sort-list/submissions/499363940/?envType=study-plan-v2&envId=top-100-liked

这里我们直接进阶，用时间复杂度O(nlogn)，空间复杂度O(1)，来解决。

        对于归并，如果自上而下的话，空间复杂度为O(n)，因为需要开辟n个结点

        所以我们要换种思路，自下而上，直接将链表看成独立的n个结点。

        首先合并算法：

struct ListNode* merge(struct ListNode* head1,struct ListNode* head2)
{
    struct ListNode* dummyHead = (struct ListNode*)malloc(sizeof(struct ListNode));
    dummyHead->val = 0,dummyHead->next = NULL;
    struct ListNode* tmp = dummyHead,*h1=head1,*h2=head2;
    while(h1 && h2)
    {
        if(h1->val <= h2->val)
        {
            tmp->next = h1;
            h1=h1->next;
        }
        else
        {
            tmp->next = h2;
            h2 = h2->next;
        }
        tmp = tmp->next;
    }
    if(h1)
    {
        tmp->next = h1;
    }
    if(h2)
    {
        tmp->next = h2;
    }
    return dummyHead->next;
}

        思路：

        这里的细节在于：找每组的子区间，找子区间的判断条件，隔离子区间，链接每一组，找下一组的子区间。

        具体代码如下：

struct ListNode* merge(struct ListNode* head1,struct ListNode* head2)
{
    struct ListNode* dummyHead = (struct ListNode*)malloc(sizeof(struct ListNode));
    dummyHead->val = 0,dummyHead->next = NULL;
    struct ListNode* tmp = dummyHead,*h1=head1,*h2=head2;
    while(h1 && h2)
    {
        if(h1->val <= h2->val)
        {
            tmp->next = h1;
            h1=h1->next;
        }
        else
        {
            tmp->next = h2;
            h2 = h2->next;
        }
        tmp = tmp->next;
    }
    if(h1)
    {
        tmp->next = h1;
    }
    if(h2)
    {
        tmp->next = h2;
    }
    return dummyHead->next;
}

struct ListNode* sortList(struct ListNode* head) {
    if(head == NULL)
        return head;
    int len = 0;//长度
    for(struct ListNode* cur = head;cur!=NULL;cur=cur->next)len++;
    
    struct ListNode* dummy = malloc(sizeof(struct ListNode));
    dummy->val = 0,dummy->next = head;

    //自底向上归并排序
    for(int sublen = 1;sublen < len;sublen*=2)
    {
        struct ListNode* pre = dummy,*cur=dummy->next;//每次从新的头开始记录
        while(cur)
        {
            struct ListNode* head1 = cur;//第一个头就是cur
            for(int i = 1;i<sublen && cur->next!=NULL;i++)//找1子区间的尾，并且2子区间不为空
            {
                cur = cur->next;
            }
            //如果for是在cur->next == NULL结束的，那2子区间头就是空
            struct ListNode* head2=cur->next;//2子区间的头
            cur->next = NULL;//将1子区间分离出来
            cur = head2;
            //再找2子区间的尾
            for(int i = 1;i<sublen && cur!=NULL;i++)
            {
                cur=cur->next;
            }

            struct ListNode* next = NULL;//记录下一组的头
            //如果cur为空，说明已经到了整个链表的最后
            if(cur != NULL)//cur不为空
            {
                next = cur->next;//记录下一组的头，可空可不空
                cur->next = NULL;//分离2子区间
            }
            struct ListNode* Merged = merge(head1,head2);//记录每次合并后的头
            pre->next = Merged;
            while(pre->next)//走到合并后的1，2区间的尾，pre来链接每一组
            {
                pre = pre->next;
            }
            cur = next;//进入下一组
        }
    }
    return dummy->next;
}