/**

 * Definition for singly-linked list.

 * function ListNode(val) {

 *     this.val = val;

 *     this.next = null;

 * }

 */

/**

 * @param {ListNode} head

 * @return {ListNode}

 */

var sortList = function(head) {

    if(head==null||head.next==null){

        return head;

    }else{

        var slow=head,fast=head;

        while(fast.next!=null&&fast.next.next!=null){

            slow=slow.next;

            fast=fast.next.next;

        }

        //拆成两个链表

        fast=slow;

        slow=slow.next;

        fast.next=null;

        fast=sortList(head);

        slow=sortList(slow);

        return merge(fast,slow);

    }

};

function merge(head1,head2){

    if(head1==null){

        return head2;

    }

    if(head2==null){

        return head1;

    }

    var res=new ListNode(),p=new ListNode();

    if(head1.val<head2.val){

        res=head1;

        head1=head1.next;

    }else{

        res=head2;

        head2=head2.next;

    }

    p=res;

    while(head1!=null&&head2!=null){

        if(head1.val<head2.val){

            p.next=head1;

            head1=head1.next;

        }else{

            p.next=head2;

            head2=head2.next;

        }

        p=p.next;

    }

    if(head1!=null){

        p.next=head1;

    }else if(head2!=null){

        p.next=head2;

    }

    return res;

}