题解 | #单链表的排序#

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 fast = head, slow = head;
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }

        ListNode rightHead = slow.next;
        slow.next = null;
        ListNode newHead = merge(sortInList(head), sortInList(rightHead));

        return newHead;
    }

    private static ListNode merge(ListNode head1, ListNode head2) {
        if (head1 == null || head1 == null) {
            return head1 == null ? head2 : head1;
        }

        ListNode dummy = new ListNode(-1);
        ListNode tmp = dummy, cur1 = head1, cur2 = head2;
        while (cur1 != null && cur2 != null) {
            if (cur1.val < cur2.val) {
                tmp.next = cur1;
                tmp = tmp.next;
                cur1 = cur1.next;
            } else {
                tmp.next = cur2;
                tmp = tmp.next;
                cur2 = cur2.next;
            }
        }

        if (cur1 != null) {
            tmp.next = cur1;
        }
        if (cur2 != null) {
            tmp.next = cur2;
        }

        return dummy.next;
    }
}