题目地址

https://leetcode-cn.com/problems/sort-list/

题目描述

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

进阶：
你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？
 
示例 1：
输入：head = [4,2,1,3]
输出：[1,2,3,4]
示例 2：
输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]
示例 3：
输入：head = []
输出：[]
 
提示：
链表中节点的数目在范围 [0, 5 * 104] 内
-105 <= Node.val <= 105

思路

暴力法，取出所有的节点，保存起来，然后将所有的节点排序，然后将排序后的节点重新组成链表，返回链表头即可。这种情况时间复杂度符合要求，但是空间复杂度不符合进阶要求，可以看下归并排序解法。

题解

/**
 * @Author: vividzcs
 * @Date: 2021/2/15 10:18 下午
 */
public class SortList {
    public static void main(String[] args) {
        int[] arr = {4,2,1,3};
        ListNode root = ListNode.createListNode(arr);
        ListNode head = sortList(root);
        ListNode.print(head);
    }

    /**
     * 执行用时：12 ms, 在所有 Java 提交中击败了27.09%的用户
     * 内存消耗：47.7 MB, 在所有 Java 提交中击败了7.40%的用户
     */
    private static ListNode sortList(ListNode root) {
        ListNode head = new ListNode(-1);
        ListNode tmp = root;
        List<ListNode> listNodes =  new ArrayList<>();
        while (tmp != null) {
            listNodes.add(tmp);
            tmp = tmp.next;
        }
        Collections.sort(listNodes, new Comparator<ListNode>() {
            @Override
            public int compare(ListNode o1, ListNode o2) {
                return o1.val - o2.val;
            }
        });
        tmp = head;
        for (int i=0; i<listNodes.size(); i++) {
            tmp.next = listNodes.get(i);
            tmp = tmp.next;
        }
        tmp.next = null;
        return head.next;
    }
}