LeetCode23:合并K个升序链表

时间:2024-11-02 20:56:49
/** * 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 mergeKLists(ListNode[] lists) { // 初始化结果链表 ListNode result = null; // 如果输入链表数组为空,直接返回null if (lists == null || lists.length == 0) { return result; } // 使用一个列表来存储所有链表中的节点值 List<Integer> array = new ArrayList<>(); // 遍历所有链表,将节点值添加到列表中 for (int i = 0; i < lists.length; i++) { node(lists[i], array); } // 如果列表为空,返回null if (array.size() == 0) { return result; } // 将列表转换为数组并排序 Integer[] ts = array.toArray(new Integer[array.size()]); Arrays.sort(ts); // 创建新链表的头节点 result = new ListNode(ts[0]); ListNode dummy = result; // 使用dummy指针帮助构建链表 // 遍历排序后的数组,构建链表 for (int i = 1; i < ts.length; i++) { ListNode temp = new ListNode(ts[i]); dummy.next = temp; // 将新节点连接到链表 dummy = temp; // 移动dummy指针 } return result; // 返回合并后的链表 } // 辅助函数:遍历链表并将节点值添加到列表中 public void node(ListNode node, List<Integer> list) { while (node != null) { list.add(node.val); // 将节点值添加到列表 node = node.next; // 移动到下一个节点 } } }