/** * Definition for singly-linked list. * public class ListNode { *     int val; *     ListNode next; *     ListNode(int x) { val = x; } * } */public class Solution {    public ListNode sortList(ListNode head) {        if(head==null || head.next==null) return head;//当分到只有一个node的时候，直接返回                ListNode mid=findMid(head);                ListNode secList=mid.next;        mid.next=null;                return mergeList(  sortList(head) , sortList(secList)  );    }        public ListNode findMid(ListNode head){ //找到中点区分上半段list和下半段list        ListNode slow=head;        ListNode fast=head;        while(fast.next!=null && fast.next.next!=null){ //让slow最终留在前半段list的末尾处，而不是后半段的第一个            slow=slow.next;            fast=fast.next.next;        }        return slow;    }        public ListNode mergeList(ListNode fst,ListNode sec){//合并list        ListNode newHead=new ListNode(0);        ListNode tmpHead=newHead;                while(fst!=null && sec!=null){            if(fst.val<=sec.val){                tmpHead.next=fst;                fst=fst.next;                tmpHead=tmpHead.next;                tmpHead.next=null;            }else{                tmpHead.next=sec;                sec=sec.next;                tmpHead=tmpHead.next;                tmpHead.next=null;            }        }        tmpHead.next=(fst==null)?sec:fst;        return newHead.next;    }}