LeetCode-148-排序链表

题目

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

示例 1：

img

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

示例 2：

img

输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]

示例 3：

输入：head = []
输出：[]

提示：

• 链表中节点的数目在范围 [0, 5 * 104] 内
• -105 <= Node.val <= 105

进阶：你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？

题解

这一题我的思路还是比较简单的，就是先遍历链表，然后保存到一个list中去，然后使用Collections.sort()对list排序，排序完成再构造新的链表返回即可。

这里需要注意Collections.sort()自定义方法，因为我后面是removeLast()，所以这里需要从大往小排，(l1, l2) -> l2.val - l1.val。

class Solution {
    public ListNode sortList(ListNode head) {
        // 先把每个节点保存到一个列表中，然后对列表进行排序，最后再构建新的链表
        List<ListNode> list = new ArrayList<>();
        while (head != null) {
            list.add(new ListNode(head.val));
            head = head.next;
        }
        Collections.sort(list, (l1, l2) -> l2.val - l1.val);
        ListNode res = new ListNode(), resHead = new ListNode();
        resHead = res;
        while (!list.isEmpty()) {
            res.next = list.removeLast();
            res = res.next;
        }
        return resHead.next;
    }
}