leetcode 148. 排序链表

2023.10.27

        由于链表不太好修改前后驱关系，所以我选择先将链表所有节点的值保存到集合nums中，然后对集合进行一个升序排序，再根据这个集合重新构造一个新的链表。

        java代码如下：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode sortList(ListNode head) {
        if(head == null) return null;
        List nums = new ArrayList<>();
        while(head != null){
            nums.add(head.val);
            head = head.next;
        }
        Collections.sort(nums);
        ListNode new_head = new ListNode(nums.get(0));
        ListNode cur = new_head;
        for(int i=1; i
            ListNode node = new ListNode(nums.get(i));
            cur.next = node;
            cur = cur.next;
        }
        return new_head;
    }
}