题目链接
题目简介
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
示例 1： 输入：lists = [[1,4,5],[1,3,4],[2,6]] 输出：[1,1,2,3,4,4,5,6] 解释：链表数组如下： [ 1->4->5, 1->3->4, 2->6 ] 将它们合并到一个有序链表中得到。 1->1->2->3->4->4->5->6
题目解析
- 题目有两种实现方法：最小堆和归并思想
- 最小堆：
- 利用
Queue queue = new PriorityQueue<>((v1, v2) -> v1.val - v2.val);生成一个最小堆 - 将我们
lists遍历一遍，放入我们的最小堆中 - 利用
minListNode = queue.poll()取出最小的，判断其next是否为空，从而判断是否添加至 ·queue· - 最后返回
newListNode即可
- 归并：
- 首先，我们必须要会两个有序链表的合并，详情请见：【 腾讯精选练习 50 题】12—合并两个有序链表【简单】
- 和归并排序差不多，两两归并，最后返回即可
题目代码
- 最小堆
public ListNode mergeKLists(ListNode[] lists) { // 最小堆的做法 Queue<ListNode> queue = new PriorityQueue<>((v1, v2) -> v1.val - v2.val); for(ListNode listNode : lists){ if(listNode != null){ queue.offer(listNode); } } ListNode newNode = new ListNode(0); ListNode p1 = newNode; while (!queue.isEmpty()){ ListNode minListNode = queue.poll(); p1.next = minListNode; p1 = p1.next; if(minListNode.next != null){ queue.offer(minListNode.next); } } return newNode; }
- 归并
class Solution { public ListNode mergeKLists(ListNode[] lists) { // 类似归并排序 // 先对于 1 2 、3 4 、5 6 return merge(lists, 0, lists.length - 1); } public ListNode merge(ListNode[] lists, int left, int right){ if(left == right){ return lists[left]; } if(left > right){ return null; } int mid = (right - left) / 2 + left; // 获取左边归并的链表 // 获取右边归并的链表 ListNode node1 = merge(lists, left, mid); ListNode node2 = merge(lists, mid + 1, right); // 最后统一进行归并 return mergeTwoListNode(node1, node2); } // 两个有序链表的归并 public ListNode mergeTwoListNode(ListNode node1, ListNode node2){ if(node1 == null){ return node2; } if(node2 == null){ return node1; } ListNode newNode = new ListNode(0); ListNode p1 = newNode; while(node1 != null && node2 != null){ if(node1.val <= node2.val){ newNode.next = node1; node1 = node1.next; newNode = newNode.next; }else{ newNode.next = node2; node2 = node2.next; newNode = newNode.next; } } while(node1 != null){ newNode.next = node1; node1 = node1.next; newNode = newNode.next; } while(node2 != null){ newNode.next = node2; node2 = node2.next; newNode = newNode.next; } return p1.next; } }
