1+ /*
2+ Author: King, wangjingui@outlook.com
3+ Date: Dec 17, 2014
4+ Problem: Merge k Sorted Lists
5+ Difficulty: easy
6+ Source: https://oj.leetcode.com/problems/merge-k-sorted-lists/
7+ Notes:
8+ Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
9+
10+ Solution: Find the smallest list-head first using minimum-heap(lgk).
11+ complexity: O(N*KlgK)
12+ */
13+
14+ /**
15+ * Definition for singly-linked list.
16+ * struct ListNode {
17+ * int val;
18+ * ListNode *next;
19+ * ListNode(int x) : val(x), next(NULL) {}
20+ * };
21+ */
22+ /**
23+ * Definition for singly-linked list.
24+ * public class ListNode {
25+ * int val;
26+ * ListNode next;
27+ * ListNode(int x) {
28+ * val = x;
29+ * next = null;
30+ * }
31+ * }
32+ */
33+ public class Solution {
34+ public ListNode mergeKLists_1 (List <ListNode >lists ) {
35+ Comparator <ListNode >comp =new Comparator <ListNode >(){
36+ public int compare (ListNode a ,ListNode b ) {
37+ if (b .val >a .val ) {
38+ return -1 ;
39+ }else if (b .val <a .val ){
40+ return 1 ;
41+ }else {
42+ return 0 ;
43+ }
44+ }
45+ };
46+
47+ Queue <ListNode >q =new PriorityQueue <ListNode >(10 ,comp );
48+ for (int i =0 ;i <lists .size (); ++i )
49+ if (lists .get (i ) !=null )
50+ q .add (lists .get (i ));
51+
52+ ListNode dummy =new ListNode (0 );
53+ ListNode cur =dummy ;
54+ while (!q .isEmpty ()) {
55+ ListNode node =q .poll ();
56+ cur =cur .next =node ;
57+ if (node .next !=null )
58+ q .add (node .next );
59+ }
60+ return dummy .next ;
61+ }
62+ ListNode mergeTwoLists (ListNode l1 ,ListNode l2 ) {
63+ ListNode head =new ListNode (0 );
64+ ListNode cur =head ;
65+ while (l1 !=null &&l2 !=null ) {
66+ if (l1 .val <l2 .val ) {
67+ cur .next =l1 ;
68+ l1 =l1 .next ;
69+ }else {
70+ cur .next =l2 ;
71+ l2 =l2 .next ;
72+ }
73+ cur =cur .next ;
74+ }
75+ if (l1 !=null )cur .next =l1 ;
76+ if (l2 !=null )cur .next =l2 ;
77+ return head .next ;
78+ }
79+ public ListNode mergeKLists (List <ListNode >lists ) {
80+ if (lists .size ()==0 )return null ;
81+ int sz =lists .size (),end =sz -1 ;
82+ while (end >0 ) {
83+ int begin =0 ;
84+ while (begin <end ) {
85+ ListNode node =mergeTwoLists (lists .get (begin ),lists .get (end ));
86+ lists .set (begin ,node );
87+ ++begin ; --end ;
88+ }
89+ }
90+ return lists .get (0 );
91+ }
92+ }
