当前位置：首页 > news >正文

33.排序链表

news 2026/5/12 18:11:26

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;}
}