Leetcode – Merge k Sorted Lists

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

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.

作者：Timshel

thou mayest rule over it.

原文地址：Leetcode – Merge k Sorted Lists, 感谢原作者分享。