题解 | #链表排序#

//归并排序
注意合并时 排序使用两个指针 ，避免两次循环的排序方法

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
      public ListNode sortList (ListNode head) {
         if(head==null||head.next==null){
            return head;
        }
        //分
        ListNode mid = getmid(head);
        ListNode head2 = mid.next;
        mid.next=null;

        head=sortList(head);
        head2=sortList(head2);
        //归
        head = merge(head,head2);
        return head;
    }

    public ListNode merge(ListNode head1,ListNode head2){
        //定义两个指针结点
        ListNode temp2 = head2;
        ListNode head = new ListNode(0);//任意设置一个临时首节点
        head.next=head1;//定义一个临时首结点
        ListNode temp1 = head;

        while(temp1.next!=null&&temp2!=null){//边界条件
            //指针移动比较两指针结点处的val值

            //如果temp1.next<temp2的val值，将temp2的val赋给node，并插入head1中， 使用temp1.next的原因是便于
            //找到比较结点的上一个节点，方便插入
            if(temp1.next.val>temp2.val){
                //temp2结点复制到node，temp2指针向后移动一位,node断链
                ListNode node = temp2;
                temp2=temp2.next;
                node.next=null;

                //将node插入到head1中,更新temp1
                node.next=temp1.next;
                temp1.next=node;
                temp1=node;
            }else{//如果>=则，temp1向后移动

                temp1=temp1.next;
            }
        }
        //若temp1.next==null，则将temp2的后续元素全部插入到temp1之后
        if(temp1.next==null){
            temp1.next=temp2;
        }
        return head.next;
    }



    public ListNode getmid(ListNode head){
        ListNode temp = head;
        int count = 1;
        while(temp.next!=null){
            temp=temp.next;
            count++;
        }
        if(count==2){
            return head;
        }
        int mid = count/2+1;
        temp = head;

        while(count!=mid){
            temp=temp.next;
            count--;
        }
        return temp;  
    }
}