题解 | #单链表的排序#

import java.util.*;

public class Solution {
    /**
     * @param head ListNode类 the head node
     * @return ListNode类

     */
     //由于时间复杂度只能采用快排，堆排，归并
        //以下代码使用归并排序，合并两个有序链表，也是归并的一个体现，
        //定义三个指针，快指针每次走两步，慢指针走一步，将链表分为两部分。
        //依次分割，分到一个时就相当于一个有序链表，然后重新组成的方式就与合并有序链表一样。
    public ListNode sortInList (ListNode head) {
        
        if(head==null||head.next==null){
            return head;
        }
        //分割链表
        ListNode left = head;
        ListNode mid = head.next;
        ListNode right = head.next.next;

         while(right != null && right.next != null){
            left = left.next;//走到中间的前驱
            mid = mid.next;//走到中间
            right = right.next.next;//走到最后
        }
        //断开得到两个链表
        left.next = null;
        //合并两个递归拆分成最小的链表，
        return merge(sortInList(head), sortInList(mid));
    }

       
    
ListNode merge(ListNode p1,ListNode p2){
        if(p1==null){
            return p2;
        }
        if(p2==null){
            return p1;
        }
          //加一个表头
        ListNode head = new ListNode(0);
        ListNode cur = head;
        //两个链表都要不为空
        while(p1 != null && p2 != null){
            //取较小值的节点
            if(p1.val <= p2.val){
                cur.next = p1;
                
                p1 = p1.next;
            }else{
                cur.next = p2;
               
                p2 = p2.next;
            }
            //指针后移
            cur = cur.next;
        }
        //哪个链表还有剩，直接连在后面
        if(p1 != null)
            cur.next = p1;
        else
            cur.next = p2;
        //返回值去掉表头
        return head.next;


        
    }

}