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