LeetCode148. Sort List

Sort a linked list in O(nlogn) time using constant space complexity

思路：归并排序

1. 主函数递归调用，那么先定义递归结束的条件
2. 找到链表的中点，分别排序前后两部分
3. 合并两个已经是有序的List

  /** sort a list. */
  public ListNode sortList(ListNode head) {
    if (head == null || head.next == null)
      return head;
    if (head.next.next == null){
      sort2Nodes(head, head.next);
    }
    else {
      ListNode mid = findMid(head);
      head = sortList(head);
      mid = sortList(mid);
      if(head.val > mid.val){
        ListNode tmp = head;
        head = mid;
        mid = tmp;
      }
      mergeList(head, mid);
    }
    return head;
  }

  /** merge two ordered lists. */
  private void mergeList(ListNode p1, ListNode p2) {
    while(p1.next != null && p2 != null){
      if(p1.val <= p2.val && p1.next.val > p2.val) {
        ListNode tmp = p1.next;
        ListNode tmp0 = p2.next;
        p1.next = p2;
        p2.next = tmp;
        p2 = tmp0;
      }
      p1 = p1.next;
    }
    if (p2 != null)
      p1.next = p2;
  }

  /** find middle node. */
  private ListNode findMid(ListNode head) {
    ListNode p1 = head, p2 = head.next.next, tmp;
    while (p2 != null && p2.next != null) {
      p1 = p1.next;
      p2 = p2.next.next;
    }
    tmp = p1.next;
    p1.next = null;
    return tmp;
  }

  /** sort list with only two nodes. */
  private void sort2Nodes(ListNode p1, ListNode p2) {
    if (p1.val > p2.val){
      int tmp = p2.val;
      p2.val = p1.val;
      p1.val = tmp;
    }
  }
```````