面试题 08.06. 汉诺塔问题

  • 时间复杂度O(nlogn)
  • 归并排序
class Solution {
    public ListNode sortList(ListNode head) {
        return sortList(head, null);
    }
	// 左右分别排序，然后合并
    public ListNode sortList(ListNode head, ListNode tail) {
        if (head == null) {
            return head;
        }
        if (head.next == tail) {
            head.next = null;
            return head;
        }
        ListNode mid = head, fast = head;
        while (fast != tail) {
            mid = mid.next;
            fast = fast.next;
            if (fast != tail) {
                fast = fast.next;
            }
        }
        ListNode left = sortList(head, mid);
        ListNode right = sortList(mid, tail);
        ListNode sorted = merge(left, right);
        return sorted;
    }
    // 合并排序
    public ListNode merge(ListNode left, ListNode right) {
        ListNode head = new ListNode(0);
        ListNode temp = head, leftTemp = left, rightTemp = right;
        while (leftTemp != null && rightTemp != null) {
            if (leftTemp.val <= rightTemp.val) {
                temp.next = leftTemp;
                leftTemp = leftTemp.next;
            }else {
                temp.next = rightTemp;
                rightTemp = rightTemp.next;
            }
            temp = temp.next;
        }
        if (leftTemp != null) {
            temp.next = leftTemp;
        } else if (rightTemp != null) {
            temp.next = rightTemp;
        }
        return head.next;
    }
}