33.排序链表

LCR 077. 排序链表

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

示例 1：

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

【思路】

利用ArrayList 记录链表中的数值val ，并排序。再逐个建立新结点 赋值 为对应排序后的 val .

注意！！！

Collections.sort(list)  对list排序 默认升序。   // 降序   Collections.sort(values, Collections.reverseOrder());

// 降序（Lambda 版） Collections.sort(values, (a, b) -> b - a);

ArrayList 获取长度应该用 idx.size()

return new ListNode() 会返回一个值为 0 的空节点，而正确的应该返回 null

/**
 * 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;
        
        // 1. 提取所有节点值到列表
        ArrayList<Integer> values = new ArrayList<>();
        ListNode cur = head;
        while (cur != null) {
            values.add(cur.val);
            cur = cur.next;
        }
        
        // 2. 对值进行排序
        Collections.sort(values);
        
        // 3. 重建排序后的链表
        ListNode dummy = new ListNode(); // 哑节点，简化链表操作
        cur = dummy;
        for (int val : values) {
            cur.next = new ListNode(val); // 新建节点，避免原节点指针干扰
            cur = cur.next;
        }
        
        return dummy.next;
    }
}