题解 | #单链表的排序#

import java.util.*;

/*

• public class ListNode {
• int val;
• ListNode next = null;
• } */

public class Solution { /** * * @param head ListNode类 the head node * @return ListNode类 */ public ListNode sortInList (ListNode head) { // write code here if(head==null||head.next==null){ return head; } ListNode slow=head; ListNode faster=head.next; while(faster!=null&&faster.next!=null){ slow=slow.next; faster=faster.next.next; } ListNode mid=slow.next; slow.next=null;

    ListNode left=sortInList(head);
    ListNode right=sortInList(mid);
    ListNode tail=new ListNode(-1);
    ListNode temp=tail;
    while(left!=null&&right!=null){
        if(left.val>=right.val){
            temp.next=right;
            right=right.next;
        }else{temp.next=left;
         
              left=left.next;
            
        }
        temp=temp.next;
    }
    if(temp!=null)
    temp.next=(left!=null)?left:right;
    return tail.next;
    
}

}