【链表】单链表的排序（归并排序）

【链表】合并k个以排序的链表（归并排序）_暮色_年华的博客-CSDN博客

 相当于合并n个有序的单链表，且每个单链表长度为1。

把单链表每个加在list中，然后套用归并排序的函数。

import java.util.*;



public class Solution {
    
    public ListNode sortInList (ListNode head) {
        // write code here
        if(head==null)return null;
        ArrayListlist=new ArrayList<>();
        ListNode p=head;
        while(p!=null){
            ListNode q=p.next;
            p.next=null;
            list.add(p);
            p=q;
        }
        return mergeKLists(list);
        
    }
       public ListNode merge(ListNode l1,ListNode l2){
        if(l1==null||l2==null){
            return l1==null?l2:l1;
        }
        ListNode dummyNode=new ListNode(-1);
        ListNode cur=dummyNode;
        while(l1!=null&&l2!=null){
            if(l1.val lists,int L,int R){
        if(L==R){
            return lists.get(L);
        }
        if(L>R)return null;
        int mid=L+((R-L)>>1);
        return merge(mergeList(lists,L,mid),mergeList(lists,mid+1,R));
    }
     public ListNode mergeKLists(ArrayList lists) {
        return mergeList(lists,0,lists.size()-1);
    }
}