Believing Process 力扣Hot148.排序链表_hothot148

题干：

给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

示例 1：
输入：head = [4,2,1,3]
输出：[1,2,3,4]

 public static ListNode sortList(ListNode head) {
         if(head==null||head.next==null) return head;
         ListNode fast = head;
         ListNode slow = head;
         while (fast.next!=null&&fast.next.next!=null){
             //快指针走两步，慢指针走一步
             fast = fast.next.next;
             slow = slow.next;
         }
         ListNode temp = slow.next;
         slow.next = null;
         //左右递归接着拆分
         ListNode left = sortList(head);
         ListNode right = sortList(temp);
         //用于返回结果的指针
         ListNode dumpy = new ListNode(0);
         //用于遍历的指针
         ListNode prev = dumpy;
         while(left!=null&&right!=null){
             //左链表的值小，拼接左链表
             if(left.val<=right.val){
                 prev.next = left;
                 left = left.next;
             }
             //右链表的值小，拼接右链表
             else{
                 prev.next = right;
                 right = right.next;
             }
             //拼接完一个节点，移动遍历指针
             prev = prev.next;
         }
         //如果左链表有剩余元素，就拼接左链表，否则拼接右链表
         prev.next = left!=null? left:right;
         //返回结果
        return dumpy.next;
    }

 归并排序，首先用快慢指针找到当前链表的中点，快指针走两步，慢指针走一步，（注意fast.next!=null&&fast.next.next!=null有区别），然后用一个临时节点temp表示中点的后一个节点，且以这个temp节点作为分割后第二个链表的头节点，继续递归左右两个链表，用一个dumpy节点表示后续需要返回的头节点，prev节点表示遍历中的节点，然后按照节点值小的在前，依次将左右链表中的节点拼接起来，最后如果左右链表还有剩余，则全部拼接起来。