首页 > 编程语言 > 详细

LeetCode 23. 合并K个排序链表

时间:2019-09-23 19:28:20      阅读:99      评论:0      收藏:0      [点我收藏+]
执行用时 :4 ms, 在所有 Java 提交中击败了98.35% 的用户
内存消耗 :38.9 MB, 在所有 Java 提交中击败了94.11%的用户
 
原本是“逐一两两合并链表”,用时118ms,换成假分治后只用4ms,震惊!代码其实就是把遍历换成了队列……
 
关键代码变化:
 
“分治”:
1 static public ListNode mergeKLists(ListNode[] lists) {
2         if (lists == null || lists.length == 0) return null;
3         Queue<ListNode> q = new ArrayDeque<>();
4         for (ListNode n : lists) if (n != null) q.add(n);
5         while (q.size() > 1) {
6             q.add(merge2(q.poll(), q.poll()));
7         }
8         return q.poll();
9     }


 

逐一两两合并链表:

1     public ListNode mergeKLists(ListNode[] lists) {
2         if (lists.length==0)return null;
3         ListNode head = lists[0];
4         for (int i = 1; i < lists.length; i++) head = merge2(head, lists[i]);
5         return head;
6     }

 

有毒……

 

 1 import java.util.ArrayDeque;
 2 import java.util.Queue;
 3 
 4 public class Solution {
 5     static public ListNode mergeKLists(ListNode[] lists) {
 6         if (lists == null || lists.length == 0) return null;
 7         Queue<ListNode> q = new ArrayDeque<>();
 8         for (ListNode n : lists) if (n != null) q.add(n);
 9         while (q.size() > 1) {
10             q.add(merge2(q.poll(), q.poll()));
11         }
12         return q.poll();
13     }
14 
15     static ListNode merge2(ListNode l1, ListNode l2) {
16         if (l1 == null) return l2;
17         if (l2 == null) return l1;
18 
19         if (l1.val > l2.val) {
20             ListNode t = l1;
21             l1 = l2;
22             l2 = t;
23         }
24 
25         ListNode head = l1;
26         while (l1 != null && l2 != null) {
27             while (l1.next != null && l1.next.val < l2.val) l1 = l1.next;
28             if (l1.next == null) {
29                 l1.next = l2;
30                 return head;
31             }
32             ListNode next = l1.next;
33             l1.next = l2;
34             while (l2.next != null && l2.next.val < next.val) l2 = l2.next;
35             ListNode t = l2;
36             l2 = l2.next;
37             t.next = next;
38             l1 = next;
39         }
40         return head;
41     }
42 }

 

LeetCode 23. 合并K个排序链表

原文:https://www.cnblogs.com/towerbird/p/11573874.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!