题解 | #单链表的排序#

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) {
        if (head == null || head.next == null) return head;
        ListNode left=head,mid=head.next,right=head.next.next;
        while (right!=null){
            left=left.next;
            mid=mid.next;
            right=right.next;
            if (right!=null)right=right.next;
        }
        left.next=null;
        return sort4(sortInList(head), sortInList(mid));
    }

    public ListNode sort4(ListNode head1, ListNode head2) {
        if (head1==null)return head2;
        if (head2==null)return head1;
        ListNode head = new ListNode(-1);
        head.val=0;
        ListNode cur = head;
        while (head1 != null||head2!=null) {
            if (head1==null) {
                cur.next = head2;
                break;
            }
            if (head2==null) {
                cur.next = head1;
                break;
            }
            if (head1.val>head2.val) {
                cur.next=head2;
                cur=head2;
                head2 = head2.next;
            } else {
                cur.next=head1;
                cur=head1;
                head1 = head1.next;
            }
        }
        return head.next;
    }
}