排序链表

题目：
在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。

示例 1:

输入: 4->2->1->3
输出: 1->2->3->4
示例 2:

输入: -1->5->3->4->0
输出: -1->0->3->4->5

思想：
可用归并排序来做，因为是链表而不是数组，可以理解为不需要借助空间。归并排序的思想在这里主要运用为依次递归地到返回链表，实际上为自底向上的合并两个有序链表的操作；前面只需要拆分为两链表即可。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */

class Solution {
  public ListNode sortList(ListNode head) {
    if(head==null) {
      return null;
    }
    if(head.next==null) {
      return head;
    }
// 利用快慢指针找到中间节点，拆分为2链表
    ListNode p1 = head;
    ListNode p2 = head;
    while(p2.next!=null) {
      p2 = p2.next;
      if(p2.next==null) {
        break;
      }
      p2 = p2.next;
      p1 = p1.next;
    }
    ListNode h1 = head;
    ListNode h2 = p1.next;
    p1.next = null;
// 根据两链表，实现两排序链表的合并
    h1 = sortList(h1);
    h2 = sortList(h2);
    return merge(h1,h2);
  }

  private ListNode merge(ListNode h1, ListNode h2) {
    if(h1==null) {
      return h2;
    }
    if(h2==null) {
      return h1;
    }
    ListNode pi = h1;
    ListNode pj = h2;
    ListNode head = null;
    if(pi.val<pj.val) {
      head = pi;
      pi = pi.next;
    }else {
      head = pj;
      pj = pj.next;
    }
    ListNode p = head;
    while(pi!=null && pj!=null) {
      if(pi.val<pj.val) {
        p.next = pi;
        pi = pi.next;
        p = p.next;
      }else {
        p.next = pj;
        pj = pj.next;
        p = p.next;
      }
    }
    while(pi!=null) {
      p.next = pi;
      pi = pi.next;
      p = p.next;
    }
    while(pj!=null) {
      p.next = pj;
      pj = pj.next;
      p = p.next;
    }
    p.next = null;
    return head;
  }
}