描述

给定一个无序单链表，实现单链表的排序(按升序排序)。

示例1

输入：
[1,3,2,4,5]

返回值：
{1,2,3,4,5}

思路

链表本身没法去排序，咱们可以借助其他的数据结构来实现排序，比如 Java 中的链表，拍好序之后在重新生成链表。

AC代码

public ListNode sortInList (ListNode head) {
        // write code here
        if (head == null) {
            return head;
        }
        // 创建集合，用来存储链表中的值
        List<Integer> list = new ArrayList<>();
        // 填充链表
        while (head != null) {
            list.add(head.val);
            head = head.next;
        }
        // 排序
        list.sort((a,b)->{return a-b;});
        ListNode dummy = new ListNode(0);
        ListNode node = dummy;
        // 生成新的链表
        for (int i = 0; i < list.size(); i ++) {
            node.next = new ListNode(list.get(i));
            node = node.next;
        }
        return dummy.next;
    }

• 时间复杂度：O(N)，链表长度
• 空间复杂度：O(N)，链表长度

最后

大家可以去 【牛客网-题库-在线编程】去练习一下。
可以去微信搜索：【蘑菇睡不着】交个朋友～
也可以扫描下方二维码。