β

Leetcode – Merge k Sorted Lists

Timshel 90 阅读

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.

作者:Timshel
thou mayest rule over it.
原文地址:Leetcode – Merge k Sorted Lists, 感谢原作者分享。

发表评论