题解 | 单链表的排序

自顶向下的归并排序

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 cur = head;
        while (cur.next != null) cur = cur.next;
        head = mergeSort(head, cur);
        return head;
    }
    
    private ListNode mergeSort(ListNode head, ListNode tail) {
        if (head != tail) {
            ListNode fast = head, slow = head, mid = slow;
            while (fast != null && fast.next != null) {
                fast = fast.next.next;
                mid = slow;
                slow = slow.next;
            }
            mid.next = null;
            ListNode left = mergeSort(head, mid);
            ListNode right = mergeSort(slow, tail);
            head = merge(left, right);
        }
        return head;
    }
    
    private ListNode merge(ListNode left, ListNode right) {
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;
        while (left != null && right != null) {
            if (left.val < right.val) {
                cur.next = left;
                left = left.next;
            } else {
                cur.next = right;
                right = right.next;
            }
            cur = cur.next;
        }
        if (left != null) cur.next = left;
        if (right != null) cur.next = right;
        return dummy.next;
    }
}