/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    static ListNode findMiddle(ListNode head){
        if(head==null) return null;
        ListNode mid=head,fast=head.next;
        while (fast!=null&&fast.next!=null){
            mid=mid.next;
            fast=fast.next.next;
        }
        return mid;
    }
    static ListNode merge(ListNode a,ListNode b){
        if(a==null)
            return b;
        if(b==null)
            return a;
        ListNode head=new ListNode(0);
        ListNode p=head;
        while (a!=null&&b!=null){
            if(a.val<b.val){
                p.next=a;
                a=a.next;
            }else{
                p.next=b;
                b=b.next;
            }
            p=p.next;
        }
        if(a==null)
            p.next=b;
        if(b==null)
            p.next=a;
        return head.next;
    }

    public static ListNode sortList(ListNode head) {
        if(head==null||head.next==null){
            return head;
        }
        ListNode mid=findMiddle(head);
        ListNode right=sortList(mid.next);
        mid.next=null;
        ListNode left=sortList(head);
        return merge(left,right);
    }
}