1+ package Algorithms .list ;
2+ import java .util .Comparator ;
3+ import java .util .List ;
4+ import java .util .PriorityQueue ;
5+
6+ import Algorithms .algorithm .others .ListNode ;
7+
8+ /**
9+ * Definition for singly-linked list.
10+ * public class ListNode {
11+ * int val;
12+ * ListNode next;
13+ * ListNode(int x) {
14+ * val = x;
15+ * next = null;
16+ * }
17+ * }
18+ */
19+ public class MergeKLists_1204 {
20+ /*
21+ SOL 1:
22+ 使用merge sort和分治法完成
23+ */
24+ public ListNode mergeKLists1 (List <ListNode >lists ) {
25+ // 记得加上这个合法性判断。
26+ if (lists ==null ||lists .size () ==0 ) {
27+ return null ;
28+ }
29+
30+ return helper (lists ,0 ,lists .size () -1 );
31+ }
32+
33+ /*
34+ l, r表示list的左右边界
35+ */
36+ public ListNode helper (List <ListNode >lists ,int l ,int r ) {
37+ if (l <r ) {
38+ int mid =l + (r -l ) /2 ;
39+
40+ /*
41+ 分治法。把问题分为2个更小的子问题：左边list的merge，和右边list的merge.
42+ 再把2个生成的解合并在一起。
43+ */
44+ return merge (helper (lists ,l ,mid ),helper (lists ,mid +1 ,r ));
45+ }
46+
47+ return lists .get (l );
48+ }
49+
50+ public ListNode merge (ListNode n1 ,ListNode n2 ) {
51+ ListNode dummy =new ListNode (0 );
52+ ListNode cur =dummy ;
53+
54+ while (n1 !=null &&n2 !=null ) {
55+ if (n1 .val <n2 .val ) {
56+ cur .next =n1 ;
57+ n1 =n1 .next ;
58+ }else {
59+ cur .next =n2 ;
60+ n2 =n2 .next ;
61+ }
62+
63+ cur =cur .next ;
64+ }
65+
66+ if (n1 !=null ) {
67+ cur .next =n1 ;
68+ }else {
69+ cur .next =n2 ;
70+ }
71+
72+ return dummy .next ;
73+ }
74+
75+ /*
76+ SOL 2:
77+ 使用 priority Queue.
78+ */
79+ public ListNode mergeKLists (List <ListNode >lists ) {
80+ // 记得加上这个合法性判断。
81+ if (lists ==null ||lists .size () ==0 ) {
82+ return null ;
83+ }
84+
85+ int size =lists .size ();
86+
87+ PriorityQueue <ListNode >q =new PriorityQueue <ListNode >(size ,
88+ new Comparator <ListNode >() {
89+ // 注意，此处参数用ListNode
90+ public int compare (ListNode o1 ,ListNode o2 ) {
91+ return o1 .val -o2 .val ;
92+ }
93+ }
94+ );
95+
96+ // Add all the head node to the priority queue.
97+ for (ListNode node :lists ) {
98+ if (node !=null ) {
99+ // Should skip the null node.s
100+ q .offer (node );
101+ }
102+ }
103+
104+ ListNode dummy =new ListNode (0 );
105+ ListNode tail =dummy ;
106+
107+ while (!q .isEmpty ()) {
108+ // get the smallest node from the queue.
109+ ListNode cur =q .poll ();
110+
111+ tail .next =cur ;
112+ tail =tail .next ;
113+
114+ // 将下一个节点补充进来。
115+ if (cur .next !=null ) {
116+ q .offer (cur .next );
117+ }
118+ }
119+
120+ return dummy .next ;
121+ }
122+ }