https://leetcode-cn.com/problems/sort-list/

• 自顶向下归并排序

  对链表自顶向下归并排序的过程如下。

  找到链表的中点，以中点为分界，将链表拆分成两个子链表。寻找链表的中点可以使用快慢指针的做法，快指针每次移动 22 步，慢指针每次移动 11 步，当快指针到达链表末尾时，慢指针指向的链表节点即为链表的中点。

  对两个子链表分别排序。

  将两个排序后的子链表合并，得到完整的排序后的链表。可以使用「21. 合并两个有序链表」的做法，将两个有序的子链表进行合并。

  /**
   * Definition for singly-linked list.
   * public class ListNode {
   *     int val;
   *     ListNode next;
   *     ListNode() {}
   *     ListNode(int val) { this.val = val; }
   *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
   * }
   */
  class Solution {
     public ListNode sortList(ListNode head) {
          if(head==null||head.next==null){
              return head;
          }
          ListNode slow = head;
          ListNode fast = head.next;
  
          while (fast!=null&&fast.next!=null){
              slow = slow.next;
              fast = fast.next.next;
          }
          ListNode head2 = slow.next;
          slow.next=null;
          return merge(sortList(head),sortList(head2));
      }
  
      private ListNode merge(ListNode head1, ListNode head2) {
          ListNode ans = new ListNode(0);
          ListNode temp1 = head1,temp2 = head2,temp = ans;
          while (temp1!=null&&temp2!=null){
              if(temp1.val<temp2.val){
                  temp.next = temp1;
                  temp1 = temp1.next;
              }else{
                  temp.next = temp2;
                  temp2 = temp2.next;
              }
              temp=temp.next;
          }
          if(temp1!=null){
              temp.next=temp1;
          }else if(temp2!=null){
              temp.next=temp2;
          }
          return ans.next;
      }
  }