Note:

分成两步，divide and merge

step 1: divide，找中点，recursion

step 2： merge two linked list

分成模块写。

Key word:

public class Solution {
  public ListNode mergeSort(ListNode head) {
    if (head == null || head.next == null) {
      return head;
    }
    ListNode mid = findMid(head);
    ListNode midNext = mid.next;
    mid.next = null;
    ListNode left = mergeSort(head);
    ListNode right = mergeSort(midNext);
    return merge(left, right);
  }

  private ListNode findMid(ListNode head) {
    if (head == null || head.next == null) {
      return head;
    }
    ListNode slow = head;
    ListNode fast = head;
    while (fast.next != null && fast.next.next != null) {
      slow = slow.next;
      fast = fast.next.next;
    }
    return slow;
  }

  private ListNode merge(ListNode one, ListNode two) {
    ListNode dummy = new ListNode(0);
    ListNode cur = dummy;
    while (one != null && two != null) {
      if (one.value <= two.value) {
        cur.next = one;
        one = one.next;
      } else {
        cur.next = two;
        two = two.next;
      }
      cur = cur.next;
    }
    if (one != null) {
      cur.next = one;
    }
    if (two != null) {
      cur.next = two;
    }
    return dummy.next;
  }
}

Complexity Analysis:

TC: O(N * logN), findMid: O(N) → 所以每层都是O(N), 但是一共logN层 → divide: O(N * log N) + merge: O(N * log N). logN层， 每层O(n)；

SC: O(logN), call stack；