本文主要是介绍从零学算法23,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
23.给你一个链表数组,每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中,返回合并后的链表。
示例 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
示例 2:
输入:lists = []
输出:[]
示例 3:
输入:lists = [[]]
输出:[]
提示:
k == lists.length
0 <= k <= 104
0 <= lists[i].length <= 500
-104 <= lists[i][j] <= 104
lists[i] 按 升序 排列
lists[i].length 的总和不超过 104
- 很容易想到的就是实现两个有序链表的合并,然后循环该链表数组即可,合并两个有序链表就不过多赘述了
-
public ListNode mergeKLists(ListNode[] lists) {if(lists.length==0)return null;ListNode pre = lists[0];for(int i=1;i<lists.length;i++){ListNode cur = lists[i];// 记录合并后的链表头节点ListNode head = new ListNode(0);// 用 temp 去连接节点ListNode temp = head;while(cur!=null || pre!=null){// 连完某个链表就直接连另一个if(cur==null){temp.next = pre;pre=pre.next;}else if(pre==null){temp.next = cur;cur=cur.next;// 否则哪个数小先连哪个节点}else if(pre.val <= cur.val){temp.next = pre;pre=pre.next;}else{temp.next = cur;cur=cur.next;}temp = temp.next;}// 更新成新链表的头节点pre = head.next;}return pre;}
- 在方法一的基础上优化,我们会想到分治法
-
public ListNode mergeKLists(ListNode[] lists) {return merge(lists, 0, lists.length-1);}// 分治public ListNode merge(ListNode[] lists, int l, int r) {if(l==r)return lists[l];if(l>r)return null;int mid =(l + r)/2;return mergeTwo(merge(lists,l,mid),merge(lists,mid+1,r));}// 合并两个链表public ListNode mergeTwo(ListNode a, ListNode b) {if (a == null || b == null) {return a != null ? a : b;}ListNode head = new ListNode(0);ListNode temp = head;while(a!=null&b!=null){if(a.val<=b.val){temp.next=a;a=a.next;}else{temp.next=b;b=b.next;}temp=temp.next;}temp.next = a==null?b:a;return head.next;}
- 还有一种不同的思路,使用优先队列,自定义一个优先队列存储每个链表当前节点以及对应的值,根据节点的值排序,这样就只需要定义一个空的头结点,然后直接不断从队列取节点添加到这个头节点后面即可,在取的过程中如果节点的 next 不为空就把 next 继续加入队列
-
class Solution {// 自定义一个类存储节点和它的值,并且重写 compareTo 保证值小的节点永远在队列首class Status implements Comparable<Status> {int val;ListNode ptr;Status(int val, ListNode ptr) {this.val = val;this.ptr = ptr;}public int compareTo(Status status2) {return this.val - status2.val;}}PriorityQueue<Status> queue = new PriorityQueue<Status>();public ListNode mergeKLists(ListNode[] lists) {// 先将每个链表的首节点入队for (ListNode node: lists) {if (node != null) {queue.offer(new Status(node.val, node));}}ListNode head = new ListNode(0);ListNode tail = head;while (!queue.isEmpty()) {// 每次取出值最小的节点Status f = queue.poll();// 拼接成新链表tail.next = f.ptr;tail = tail.next;// 然后将取出的节点的下一个节点入队(如果有下一个节点)if (f.ptr.next != null) {queue.offer(new Status(f.ptr.next.val, f.ptr.next));}}return head.next;}}
这篇关于从零学算法23的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!