本文共 2465 字，大约阅读时间需要 8 分钟。

题目描述

在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。示例 1:输入: 4->2->1->3输出: 1->2->3->4示例 2:输入: -1->5->3->4->0输出: -1->0->3->4->5来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/sort-list著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

1、使用归并排序进行解决

2、首先进行分组，归并的区间按照1,2,4,8,16逐渐递增

3、然后找到要归并的链表头p和q进行归并

4、start的意思就是链表的开头

5、l用来表示每次归并完的链表头

6、flag表示在一次合并中下一次起始的节点

通过代码

class Solution {
       public ListNode sortList(ListNode head) {
           if (head==null) return null;        ListNode k=head;        int num=0;        while(k!=null){
               num++;            k=k.next;        }        ListNode start =new ListNode(0);        start.next=head;        ListNode flag=head;        ListNode l=start;        for(int base=1;num>base;base*=2){
               head=l.next;            start= new ListNode(0);            l=start;            ListNode p=head;            flag=head;            int pause=0;            while (flag!=null){
                   pause=0;                p=flag;                int count=base;                ListNode q=p;                while(count--!=0){
                       q=q.next;                    if (q==null){
                           pause=1;                        break;                    }                }                if (pause==1){
                       break;                }                int count1=base;                flag=q;                while(count1--!=0&&flag!=null){
                       flag=flag.next;                }                //比较的起点p和q已经找到                int c1=base,c2=base;                //归并链表                for(;(c1!=0)&&(c2!=0)&&(p!=null)&&(q!=null);){
                       if (p.val>q.val){
                           start.next=q;                        q=q.next;                        c2--;                    }else{
                           start.next=p;                        p=p.next;                        c1--;                    }                    start=start.next;                }                //如果p链表还没合并完                while (c1!=0&&p!=null){
                       start.next=p;                    p=p.next;                    start=start.next;                    c1--;                }                //如果q链表还没合并完                while (c2!=0&&q!=null){
                       start.next=q;                    q=q.next;                    start=start.next;                    c2--;                }                start.next=flag;            }        }        return l.next;    }}