Repository navigation
Expand file tree
/
Copy pathmergelist.py
More file actions
executable file
·103 lines (87 loc) · 2.4 KB
/
Copy pathmergelist.py
File metadata and controls
executable file
·103 lines (87 loc) · 2.4 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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#!/usr/bin/env python
#-*- coding: utf-8 -*-
import os,re,sys,commands,glob,heapq
# Definition for singly-linked list.
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class PriorityQueue:
def __init__(self):
self._queue = []
def put(self, item, priority):
heapq.heappush(self._queue, (-priority, item))
def get(self):
return heapq.heappop(self._queue)[-1]
def empty(self):
return len(self._queue) == 0
def listToNodes(l):
if not l:
return None
head = node = ListNode(0)
for x in l:
n = ListNode(x)
node.next = n
node = n
return head.next
def nodesToList(node):
l = []
while node:
l.append(node.val)
node = node.next
return l
class Solution:
# @param a list of ListNode
# @return a ListNode
def mergeKLists(self, lists):
q = PriorityQueue()
for node in lists:
if node:
q.put(node, -node.val)
r = []
while not q.empty():
node = q.get()
r.append(node.val)
node = node.next
if node:
q.put(node, -node.val)
return listToNodes(r)
class ListSolution:
# @param a list of ListNode
# @return a ListNode
def mergeKLists(self, lists):
lists = [x[:] for x in lists if x];
r = []
while lists:
firsts = [x[0] for x in lists]
first = min(firsts)
r.append(first)
i = 0;
for l in lists:
if l[0] == first:
del l[0]
if not l:
del lists[i]
break
i = i + 1
return r
def resolve(lists):
node = Solution().mergeKLists([listToNodes(l) for l in lists])
return nodesToList(node)
def testBasic():
assert resolve([[1, 2], [4, 5]]) == [1, 2, 4,5]
assert resolve([[1, 2], [4]]) == [1, 2, 4]
assert resolve([[1], [4]]) == [1, 4]
assert resolve([[1], [1, 2]]) == [1, 1, 2]
assert resolve([[1, 1], [1, 2]]) == [1, 1, 1, 2]
assert resolve([[], [1, 2]]) == [1, 2]
assert resolve([[], []]) == []
def test1():
lists = eval(open("in.txt").read())
print >> sys.stderr, (len(lists))
resolve(lists)
def main(args):
test1()
pass
if __name__ == '__main__':
main(sys.argv[1:])