Leetcode – Merge k Sorted Lists
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
思路总结
遍历多个链表,按照val排序加入列表,然后遍历列表,每个node.next = 下个node
Python
from operator import attrgetter
class Solution:
# @param a list of ListNode
# @return a ListNode
def mergeKLists(self, lists):
sortedList = []
for l in lists:
cur = l
while cur:
sortedList.append(cur)
cur = cur.next
sortedList = sorted(sortedList, key = attrgetter('val'))
for i in range(len(sortedList)-1):
sortedList[i].next = sortedList[i+1]
if len(sortedList) > 0:
sortedList[len(sortedList)-1].next = None
if sortedList:
return sortedList[0]
else:
return None
Java
public class Solution {
public ListNode mergeKLists(ListNode[] lists) {
Queue<ListNode> queue = new PriorityQueue(new Comparator<ListNode>(){
@Override
public int compare(ListNode node1, ListNode node2){
return node1.val - node2.val;
}
});
for (ListNode l : lists){
if (l!= null) queue.add(l);
}
ListNode dummy = new ListNode(0);
ListNode ret = dummy;
while(!queue.isEmpty()){
ret.next = queue.poll();
ret = ret.next;
if (ret.next != null) {
queue.offer(ret.next);
}
}
return dummy.next;
}
}
The post Leetcode – Merge k Sorted Lists appeared first on Timshel.