题目描述

描述
给定一个无序单链表，实现单链表的排序(按升序排序)。
示例1
输入：
[1,3,2,4,5]
返回值：
{1,2,3,4,5}

解题思路

暴力排序法 时间复杂度为O( ),空间复杂度为O(n)

1. 借助于 list.sort()方法，把链表所有阶段放入list进行排序
2. 排序完成后再次从头到尾连接

    public ListNode sortInList (ListNode head) {
        ListNode root;
        ListNode next = head;
        ListNode node;
        Comparator<ListNode> comparator = Comparator.comparingInt(o -> o.val);
        List<ListNode> list = new ArrayList<>();
        while(next != null){
            // 将链表节点添加到list
            list.add(next);
            next = next.next;
        }
        // 排序
        list.sort(comparator);
        // 重新赋值root
        root = list.get(0);
        node = root;
        for(int i = 1 ; i < list.size() ;i++){
            // 顺序链接链表
            root.next = list.get(i);
            root = root.next;
            if(i == list.size() -1){
                root.next = null;
            }
        }
        return node;
    }

对于取值进行排序再赋值 时间复杂度为O( ),空间复杂度为O(n)

1. 拿出每个节点的值
2. 对于节点值的集合进行排序
3. 顺序赋值
   ```
   ` public ListNode sortInList (ListNode head) {

    List<Integer> list = new ArrayList<>();
    ListNode root = head;
    while (head != null){
       // 将链表节点值加入list
        list.add(head.val);
        head = head.next;
    }
    Comparator<Integer> comparator = Comparator.comparingInt(o -> o);
    // 排序
    list.sort(comparator);
    // 记录下root
    head = root;
    int count = 0;
    while (root != null){
        int value = list.get(count);
        count++;
        // 重新赋值
        root.val = value;
        root = root.next;
    }
    return head;

   }