解法一分析这里涉及到小顶堆(优先队列)的知识。我们先来简单介绍一下小顶堆Min-Heap是一种完全二叉树结构同时满足「堆性质」每个父节点的值都小于等于其左右子节点的值因此堆顶根节点永远是整个堆中最小的元素。优先队列Priority Queue是一种抽象数据结构逻辑上通常用堆来实现而非普通队列的先进先出小顶堆实现的优先队列会保证每次取出的都是当前队列中最小的元素。具体关于堆的知识可以看这个视频【从堆的定义到优先队列、堆排序】 10分钟看懂必考的数据结构——堆_哔哩哔哩_bilibili首先这lists里面的K个链表都是升序排列好的我们首先将这K个链表的头节点全部放入一个最小堆(优先队列)中所有的头节点是有大小的或者相等。这个优先队列通过Lambda表达式指定升序排序意思就是处在优先队列的头上的元素一定是最小的。我们把这个最小的头节点加入了新链表就把它向后移动把他第二个元素offer到优先队列中。优先队列会自动升序排序就这样利用一个while循环不断地从里面poll出那个最小的元素放入新的链表中最后优先队列为空时我们也就将K个队列合并好了。下面举个例子走一遍这个流程思路会更加清晰详细操作流程以 3 个升序链表为例假设输入 lists [1-4-5, 1-3-4, 2-6] 初始堆中包含节点 [1, 1, 2] 堆顶是 1 。第 1 轮循环1. pq.poll() 取出堆顶最小节点 node 1 来自第一个链表。2. 入堆检查 node.next 是 4 非空执行 pq.offer(4) 。此时堆中剩余 [1, 2, 4] 。3. 拼接链表 cur.next node 新链表从空变为 1 。4. 指针移动 cur 指向刚拼接的节点 1 。第 2 轮循环1. pq.poll() 堆顶最小节点是 1 来自第二个链表取出 node 1 。2. 入堆检查 node.next 是 3 非空执行 pq.offer(3) 。此时堆中剩余 [2, 3, 4] 。3. 拼接链表 cur.next node 新链表变为 1-1 。4. 指针移动 cur 指向刚拼接的节点 1 。第 3 轮循环1. pq.poll() 堆顶最小节点是 2 取出 node 2 。2. 入堆检查 node.next 是 6 非空执行 pq.offer(6) 。此时堆中剩余 [3, 4, 6] 。3. 拼接链表 cur.next node 新链表变为 1-1-2 。4. 指针移动 cur 指向刚拼接的节点 2 。后续循环以此类推不断重复「取堆顶最小节点 → 后续节点入堆 → 拼接节点 → 指针后移」的过程直到堆为空。最终拼接出的完整链表为 1-1-2-3-4-4-5-6 。复杂度分析时间复杂度O(Llogm)其中 m 为 lists 的长度L 为所有链表的长度之和。空间复杂度O(m)。堆中至多有 m 个元素。具体代码实现如下class Solution { public ListNode mergeKLists(ListNode[] lists) { //最小堆即优先队列 PriorityQueueListNode pq new PriorityQueue((a,b) - a.val - b.val);//指定升序规则 //把所有非空链表的头节点入堆 for(ListNode head : lists){ if(head ! null){ pq.offer(head); } } //哑节点用于合并后的新链表 ListNode dummy new ListNode(); ListNode cur dummy; while(!pq.isEmpty()){ //pq中的最小结点 ListNode node pq.poll(); //判断并把以这个node为head的链表下一个节点加入pq if(node.next ! null){ pq.offer(node.next); } cur.next node; //把最小节点接入新链表 cur cur.next;//移动指针 } return dummy.next; } }第二种解法类似于归并加合并两个链表不断地把K个链表进行切分最后两两归并成新链表复杂度分析时间复杂度O(Llogm)其中 m 为 lists 的长度L 为所有链表的长度之和。每个节点参与链表合并的次数为 O(logm) 次一共有 L 个节点所以总的时间复杂度为 O(Llogm)。空间复杂度O(logm)。递归深度为 O(logm)需要 O(logm) 的栈空间。class Solution { public ListNode mergeKLists(ListNode[] lists) { //切分K个链表两两进行归并 return mergeKLists(lists,0,lists.length); } public ListNode mergeKLists(ListNode[] lists,int i,int j){ int m j -i; if(m 0){ return null; } if(m 1){ return lists[i]; } ListNode left mergeKLists(lists, i , im/2); ListNode right mergeKLists(lists, im/2, j); return mergerTwoLists(left,right); } private ListNode mergerTwoLists(ListNode list1,ListNode list2){ ListNode dummy new ListNode(); ListNode cur dummy; while(list1 ! null list2 ! null){ if(list1.val list2.val){ cur.next list1; list1 list1.next; }else{ cur.next list2; list2 list2.next; } cur cur.next; } cur.next list1 ! null? list1 :list2; return dummy.next; } }还有第三种自底向上进行合并链表感兴趣的可以直接点下面连接查看我只是对这道题根据个人理解进行一个简单的总结。然后今天还写了LeetCode136.只出现一次的数字总结一下主要涉及到的知识点异或运算XOR基础异或Exclusive OR符号 ^ 是一种位运算核心规则是相同为 0不同为 1。1. 基本运算规则- 0 ^ 0 0- 0 ^ 1 1- 1 ^ 0 1- 1 ^ 1 0也可以理解为不进位的二进制加法110不进位。2. 核心性质这些性质是异或解题的关键1. 交换律 a ^ b b ^ a2. 结合律 (a ^ b) ^ c a ^ (b ^ c)3. 自反性 a ^ a 0 a ^ 0 a- 推论 a ^ b ^ b a 一个数异或同一个数两次结果不变4. 归零律任何数和自身异或结果为 05. 恒等律任何数和 0 异或结果等于它本身位运算知识参考作者灵茶山艾府链接https://leetcode.cn/problems/merge-k-sorted-lists/solutions/2384305/liang-chong-fang-fa-zui-xiao-dui-fen-zhi-zbzx/
LeetCode hot100-合并K个升序链表
解法一分析这里涉及到小顶堆(优先队列)的知识。我们先来简单介绍一下小顶堆Min-Heap是一种完全二叉树结构同时满足「堆性质」每个父节点的值都小于等于其左右子节点的值因此堆顶根节点永远是整个堆中最小的元素。优先队列Priority Queue是一种抽象数据结构逻辑上通常用堆来实现而非普通队列的先进先出小顶堆实现的优先队列会保证每次取出的都是当前队列中最小的元素。具体关于堆的知识可以看这个视频【从堆的定义到优先队列、堆排序】 10分钟看懂必考的数据结构——堆_哔哩哔哩_bilibili首先这lists里面的K个链表都是升序排列好的我们首先将这K个链表的头节点全部放入一个最小堆(优先队列)中所有的头节点是有大小的或者相等。这个优先队列通过Lambda表达式指定升序排序意思就是处在优先队列的头上的元素一定是最小的。我们把这个最小的头节点加入了新链表就把它向后移动把他第二个元素offer到优先队列中。优先队列会自动升序排序就这样利用一个while循环不断地从里面poll出那个最小的元素放入新的链表中最后优先队列为空时我们也就将K个队列合并好了。下面举个例子走一遍这个流程思路会更加清晰详细操作流程以 3 个升序链表为例假设输入 lists [1-4-5, 1-3-4, 2-6] 初始堆中包含节点 [1, 1, 2] 堆顶是 1 。第 1 轮循环1. pq.poll() 取出堆顶最小节点 node 1 来自第一个链表。2. 入堆检查 node.next 是 4 非空执行 pq.offer(4) 。此时堆中剩余 [1, 2, 4] 。3. 拼接链表 cur.next node 新链表从空变为 1 。4. 指针移动 cur 指向刚拼接的节点 1 。第 2 轮循环1. pq.poll() 堆顶最小节点是 1 来自第二个链表取出 node 1 。2. 入堆检查 node.next 是 3 非空执行 pq.offer(3) 。此时堆中剩余 [2, 3, 4] 。3. 拼接链表 cur.next node 新链表变为 1-1 。4. 指针移动 cur 指向刚拼接的节点 1 。第 3 轮循环1. pq.poll() 堆顶最小节点是 2 取出 node 2 。2. 入堆检查 node.next 是 6 非空执行 pq.offer(6) 。此时堆中剩余 [3, 4, 6] 。3. 拼接链表 cur.next node 新链表变为 1-1-2 。4. 指针移动 cur 指向刚拼接的节点 2 。后续循环以此类推不断重复「取堆顶最小节点 → 后续节点入堆 → 拼接节点 → 指针后移」的过程直到堆为空。最终拼接出的完整链表为 1-1-2-3-4-4-5-6 。复杂度分析时间复杂度O(Llogm)其中 m 为 lists 的长度L 为所有链表的长度之和。空间复杂度O(m)。堆中至多有 m 个元素。具体代码实现如下class Solution { public ListNode mergeKLists(ListNode[] lists) { //最小堆即优先队列 PriorityQueueListNode pq new PriorityQueue((a,b) - a.val - b.val);//指定升序规则 //把所有非空链表的头节点入堆 for(ListNode head : lists){ if(head ! null){ pq.offer(head); } } //哑节点用于合并后的新链表 ListNode dummy new ListNode(); ListNode cur dummy; while(!pq.isEmpty()){ //pq中的最小结点 ListNode node pq.poll(); //判断并把以这个node为head的链表下一个节点加入pq if(node.next ! null){ pq.offer(node.next); } cur.next node; //把最小节点接入新链表 cur cur.next;//移动指针 } return dummy.next; } }第二种解法类似于归并加合并两个链表不断地把K个链表进行切分最后两两归并成新链表复杂度分析时间复杂度O(Llogm)其中 m 为 lists 的长度L 为所有链表的长度之和。每个节点参与链表合并的次数为 O(logm) 次一共有 L 个节点所以总的时间复杂度为 O(Llogm)。空间复杂度O(logm)。递归深度为 O(logm)需要 O(logm) 的栈空间。class Solution { public ListNode mergeKLists(ListNode[] lists) { //切分K个链表两两进行归并 return mergeKLists(lists,0,lists.length); } public ListNode mergeKLists(ListNode[] lists,int i,int j){ int m j -i; if(m 0){ return null; } if(m 1){ return lists[i]; } ListNode left mergeKLists(lists, i , im/2); ListNode right mergeKLists(lists, im/2, j); return mergerTwoLists(left,right); } private ListNode mergerTwoLists(ListNode list1,ListNode list2){ ListNode dummy new ListNode(); ListNode cur dummy; while(list1 ! null list2 ! null){ if(list1.val list2.val){ cur.next list1; list1 list1.next; }else{ cur.next list2; list2 list2.next; } cur cur.next; } cur.next list1 ! null? list1 :list2; return dummy.next; } }还有第三种自底向上进行合并链表感兴趣的可以直接点下面连接查看我只是对这道题根据个人理解进行一个简单的总结。然后今天还写了LeetCode136.只出现一次的数字总结一下主要涉及到的知识点异或运算XOR基础异或Exclusive OR符号 ^ 是一种位运算核心规则是相同为 0不同为 1。1. 基本运算规则- 0 ^ 0 0- 0 ^ 1 1- 1 ^ 0 1- 1 ^ 1 0也可以理解为不进位的二进制加法110不进位。2. 核心性质这些性质是异或解题的关键1. 交换律 a ^ b b ^ a2. 结合律 (a ^ b) ^ c a ^ (b ^ c)3. 自反性 a ^ a 0 a ^ 0 a- 推论 a ^ b ^ b a 一个数异或同一个数两次结果不变4. 归零律任何数和自身异或结果为 05. 恒等律任何数和 0 异或结果等于它本身位运算知识参考作者灵茶山艾府链接https://leetcode.cn/problems/merge-k-sorted-lists/solutions/2384305/liang-chong-fang-fa-zui-xiao-dui-fen-zhi-zbzx/
