题解 | #单链表的排序#

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类 the head node
     * @return ListNode类
     */
    public ListNode sortInList (ListNode head) {
         // 1. 排除特殊情况
         if (head==null||head.next==null) {
            return head;
        }
        // 2.切割链表
        ListNode slow = head;
        ListNode fast = head.next;
        while(fast!=null&&fast.next!=null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        // slow 即链表中点，沿着链表中间节点切割
        ListNode temp =  slow.next;
        slow.next =null;
        // 3.分别遍历两个链表进行排序
        ListNode left = sortInList(head);
        ListNode right = sortInList(temp);
        // 4.创建新的链表
        ListNode mergeList = new ListNode(0);
        ListNode res = mergeList;
        while (left!=null&&right!=null) {
            if (left.val<right.val) {
                mergeList.next = left;
                left = left.next;
            }else {
                mergeList.next = right;
                right=right.next;
            }
            mergeList = mergeList.next;
        }
        System.out.println();
        // 最后添加未对比的链表部分判断左链表是否为空
        mergeList.next = left != null ? left : right;
        return res.next;
    }
}

归并排序：递归+合并