题解 | #单链表的排序#

解题思路：

1. 要求的是空间复杂度是O(n), 时间复杂度是nlog(n)。明显就是要使用快排的思想进行排序，排序后重建链表
2. 把所有节点都添加到列表中，然后借助Collections进行升序排列，
3. 排序后进行链表的重建。注意：最后的一个尾结点的next指针要设置成null，才能避免陷入死循环。

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;
        }
        List<ListNode> list = new LinkedList<>();
        ListNode curr = head;
        while (curr != null) {
            list.add(curr);
            curr = curr.next;
        }

        Collections.sort(list, new Comparator<ListNode>() {
            @Override
            public int compare(ListNode o1, ListNode o2) {
                return o1.val - o2.val;
            }
        });

        ListNode newHead = null;
        curr = null;
        for (ListNode listNode : list) {
             listNode.next = null;
            if (newHead == null) {
                newHead = listNode;
                curr = newHead;
            } else {
                curr.next = listNode;
                 curr = curr.next;
            }
        }
        return newHead;
    }
}