[LintCode] Merge K Sorted Lists [DC/Heap]

happyhuangjinjin 发布于2019-08-14 15:32 / 2532人阅读

摘要：分治做法中，函数依然是将链表结点两两进行比较，然后在函数中迭代两个二分后的结果。

Problem

Merge k sorted linked lists and return it as one sorted list.

Analyze and describe its complexity.

Example

Given lists:

[
  2->4->null,
  null,
  -1->null
],

return -1->2->4->null.

Note

分治做法中，merge()函数依然是将链表结点两两进行比较，然后在sort()函数中迭代merge两个二分后sort()的结果。PriorityQueue更为简洁。

Solution

Divide & Conquer

public class Solution {
    public ListNode mergeKLists(List lists) {  
        if (lists == null || lists.size() == 0) return null;
        return sort(lists, 0, lists.size()-1);
    }
    public ListNode sort(List lists, int start, int end) {
        if (start < end) {
            int mid = (start+end)/2;
            return merge(sort(lists, start, mid), sort(lists, mid+1, end));
        }
        return lists.get(start);
    }
    public ListNode merge(ListNode n1, ListNode n2) {
        ListNode head = new ListNode(0);
        ListNode cur = head;
        while (n1 != null && n2 != null) {
            if (n1.val < n2.val) {
                cur.next = n1;
                n1 = n1.next;
            }
            else {
                cur.next = n2;
                n2 = n2.next;
            }
            cur = cur.next;
        }
        if (n1 != null) cur.next = n1;
        else cur.next = n2;
        return head.next;
    }
}

Priority Queue

Edited: 2018.3

public class Solution {
    public ListNode mergeKLists(List lists) {  
        if (lists == null || lists.size() == 0) return null;
        ListNode dummy = new ListNode(0);
        ListNode head = dummy;
        PriorityQueue pq = new PriorityQueue (1, new Comparator (){
            public int compare(ListNode n1, ListNode n2) {
                return n1.val - n2.val;
            }
        });
        for (int i = 0; i < lists.size(); i++) {
            if (lists.get(i) != null) pq.offer(lists.get(i));
        }
        while (!pq.isEmpty()) {
            head.next = pq.poll();
            head = head.next;
            //put the rest ListNode back to pq
            if (head.next != null) pq.offer(head.next);
        }
        return dummy.next;
    }
}

PriorityQueue Java 8

public class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;
        PriorityQueue heap = new PriorityQueue<>((n1, n2) -> n1.val-n2.val);
        for (ListNode n: lists) {
            if (n != null) heap.offer(n);
        }
        ListNode head = new ListNode(0);
        ListNode cur = head;
        while (!heap.isEmpty()) {
            cur.next = heap.poll();
            cur = cur.next;
            if (cur.next != null) heap.offer(cur.next);
        }
        return head.next;
    }
}

私有云云服务器 Lists LintCode Sorted LintCode134_LRU

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/65838.html

[LintCode/LeetCode] Merge Two Sorted Lists

摘要：先考虑和有无空集，有则返回另一个。新建链表，指针将和较小的放在链表顶端，然后向后遍历，直到或之一为空。再将非空的链表放在后面。 Problem Merge two sorted (ascending) linked lists and return it as a new sorted list. The new sorted list should be made by splici...

dockerclub 2019-08-14 15:22 评论0 收藏0
[LintCode/LeetCode] Merge Sorted Array

Problem Given two sorted integer arrays A and B, merge B into A as one sorted array. Notice You may assume that A has enough space (size that is greater or equal to m + n) to hold additional elements ...

summerpxy 2019-08-14 15:41 评论0 收藏0
[LintCode] Merge Sorted Array II

摘要：循环里最好先考虑和其中之一已经处理完的情况，就直接顺序放另一个没处理完的即可。然后再在里展开方法。避免其中一个数组较小会浪费效率的情况。丫把参数又换成了。。。 Problem Merge two given sorted integer array A and B into a new sorted integer array. Example A=[1,2,3,4] B=[2,4,5...

宠来也 2019-08-14 15:12 评论0 收藏0
[Leetcode] Merge Two Sorted Lists Merge K Sorted L

摘要：注意因为堆中是链表节点，我们在初始化堆时还要新建一个的类。代码初始化大小为的堆拿出堆顶元素将堆顶元素的下一个加入堆中 Merge Two Sorted Lists 最新更新请见：https://yanjia.me/zh/2019/01/... Merge two sorted linked lists and return it as a new list. The new list...

stefanieliang 2019-08-14 12:30 评论0 收藏0
[LeetCode] 23. Merge k Sorted Lists

摘要：思路这题中的中，个还有其中个别的等于的情况，所以要判断一下再加入代码 Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity. Heap Time Complexity: Update the heap costs O(nklogk) Space ...

Codeing_ls 2019-08-15 12:25 评论0 收藏0