题解 | #单链表的排序#

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) {
        // write code here
        if (head == null || head.next == null) {
            return head;
        }
        // 保存当前结点
        ListNode pre = head;
        // 保存下一结点
        ListNode cur = head.next;
        // 找到中间节点
        while (cur != null && cur.next != null) {
            pre = pre.next;
            cur = cur.next.next;
        }
        // 中间节点为
        ListNode mid = pre.next;
        pre.next = null;
        ListNode left = sortInList(head);
        ListNode right = sortInList(mid);
        ListNode listNode = mergerListNode(left, right);
        return listNode;
    }

    // 合并
    public ListNode mergerListNode(ListNode left, ListNode right) {
        if(left == null) {
            return right;
        }

        if(right == null) {
            return left;
        }
        ListNode newNode = new ListNode(0);
        ListNode tail = newNode;
        while (left != null && right != null) {
            if (left.val > right.val) {
                newNode.next = right;
                right = right.next;
            } else {
                newNode.next = left;
                left = left.next;
            }
            newNode = newNode.next;
        }
        if (left != null) {
            newNode.next = left;
        } else {
            newNode.next = right;
        }
        return tail.next;
    }

}