题目地址：148. 排序链表

暴力解法

暴力思路很简单,Get all the elements of the linked list,然后排序,Build a new linked list.

public ListNode sortList(ListNode head) {
    
    List<Integer> list = new ArrayList<>();
    while (head!=null){
    
        list.add(head.val);
        head=head.next;
    }
    int[] array = list.stream().mapToInt(Integer::intValue).toArray();
    Arrays.sort(array);
    ListNode listNode = new ListNode();
    ListNode res = listNode;
    for (int i : array) {
    
        listNode.next = new ListNode(i);
        listNode = listNode.next;
    }
    return res.next;
}

进阶——归并排序

进阶：你可以在 O(n log n) 时间复杂度和常数级空间复杂度下,对链表进行排序吗？
要求 O(n log n）时间复杂度,There are quick sort, heap sort, merge sort, etc,But due to the inconvenience of pointers,There is no doubt that using merge is better here.
There are several caveats to using merge on linked lists

1. Setting up a unified head node is easy to operate
2. to guarantee constant space,When merging two by two, use the cutting list：Each time according to the current merged step size,Cut into the currently required string,Then return to the back head,This ensures space,Continuity is also guaranteed.

public ListNode sortList(ListNode head) {
    
      ListNode dummyNode = new ListNode(0);
        //Unified tail node
        dummyNode.next = head;
        //每次两个 遍历
        int len =0;
        while(head!=null){
    
            head=head.next;
            len++;
        }
        ListNode work;
        ListNode tail;
        for (int step = 1; step < len; step<<=1) {
    
// 开始操作
            //左侧第一个节点
            work = dummyNode.next;
            //
            tail = dummyNode;
            while (work!=null){
    
                
                //tail用来拼接
                ListNode left = work;
                ListNode right = cut(left,step);
                //cut Don't cut it off directly at the back left-step
                work = cut(right,step);
                //merge
                tail.next=merge(left,right);
                while (tail.next!=null){
    
                    tail=tail.next;
                }
            }
        }
        return dummyNode.next;
    }
    private ListNode cut(ListNode left, int step) {
    
        while (--step!=0 && left!=null  ){
    
            left=left.next;
        }
        //Cut the current one with the next one,and will return later
        if(left!=null){
    
            ListNode result = left.next;
            left.next = null;
            return result;
            //If there is no more within the specified step size,直接返回空值
        }else{
    
            return null;
        }
    }

    private static ListNode merge(ListNode list1, ListNode list2) {
    
        ListNode res = new ListNode(0);
        ListNode sorted = res;
        while (list1 !=null && list2!=null){
    
            if(list1.val<list2.val){
    
                res.next=list1;
                list1=list1.next;
            }else {
    
                res.next=list2;
                list2=list2.next;
            }
            res= res.next;
        }
        if(list1 == null){
    
            res.next=list2;
        }else {
    
            res.next = list1;
        }
        return sorted.next;
    }