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

• 自頂向下歸并排序

  對鏈表自頂向下歸并排序的過程如下。

  找到鏈表的中點(diǎn)，以中點(diǎn)為分界，將鏈表拆分成兩個子鏈表。尋找鏈表的中點(diǎn)可以使用快慢指針的做法，快指針每次移動 22 步，慢指針每次移動 11 步，當(dāng)快指針到達(dá)鏈表末尾時，慢指針指向的鏈表節(jié)點(diǎn)即為鏈表的中點(diǎn)。

  對兩個子鏈表分別排序。

  將兩個排序后的子鏈表合并，得到完整的排序后的鏈表?？梢允褂谩?1. 合并兩個有序鏈表」的做法，將兩個有序的子鏈表進(jìn)行合并。

  /**
   * 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;
      }
  }