[Leetcode] Merge Two Sorted Lists Merge K Sorted L

stefanieliang 发布于2019-08-14 12:30 / 2867人阅读

摘要：注意因为堆中是链表节点，我们在初始化堆时还要新建一个的类。代码初始化大小为的堆拿出堆顶元素将堆顶元素的下一个加入堆中

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 should be made by splicing together the nodes of the first two lists.

依次拼接 复杂度

时间 O(N) 空间 O(1)

思路

该题就是简单的把两个链表的节点拼接起来，我们可以用一个Dummy头，将比较过后的节点接在这个Dummy头之后。最后如果有没比较完的，说明另一个list的值全比这个list剩下的小，而且拼完了，所以可以把剩下的直接全部接上去。

代码

public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        // 创建一个dummy头，从后面开始接
        ListNode dummy = new ListNode(0);
        ListNode curr = dummy;
        // 依次比较拼接
        while(l1 != null && l2 != null){
            if(l1.val <= l2.val){
                curr.next = l1;
                l1 = l1.next;
            } else {
                curr.next = l2;
                l2 = l2.next;
            }
            curr = curr.next;
        }
        // 把剩余的全拼上去
        if(l1 == null){
            curr.next = l2;
        } else if (l2 == null){
            curr.next = l1;
        }
        return dummy.next;
    }
}

Merge k Sorted Lists

最新解法请见：https://yanjia.me/zh/2019/01/...

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
Example:
Input:
[
 1->4->5,
 1->3->4,
 2->6
]
Output: 1->1->2->3->4->4->5->6

优先队列 复杂度

时间 O(NlogK) 空间 O(K)

思路

当我们归并k个列表时，最简单的方法就是，对于每次插入，我们遍历这K个列表的最前面的元素，找出K个中最小的再加入到结果中。不过如果我们用一个优先队列（堆），将这K个元素加入再找堆顶元素，每次插入只要logK的复杂度。当拿出堆顶元素后，我们再将它所在链表的下一个元素拿出来，放到堆中。这样直到所有链表都被拿完，归并也就完成了。

注意

因为堆中是链表节点，我们在初始化堆时还要新建一个Comparator的类。

代码

Java

public class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists.length == 0) return null;
        ListNode dummy = new ListNode(0);
        PriorityQueue q = new PriorityQueue(11, new Comparator(){
            public int compare(ListNode n1, ListNode n2){
                return n1.val - n2.val;
            }
        });
        // 初始化大小为k的堆
        for(int i = 0; i < lists.length; i++){
            if(lists[i] != null) q.offer(lists[i]);
        }
        ListNode curr = dummy;
        while(!q.isEmpty()){
            // 拿出堆顶元素
            curr.next = q.poll();
            curr = curr.next;
            // 将堆顶元素的下一个加入堆中
            if(curr.next != null){
                q.offer(curr.next);    
            }
        }
        return dummy.next;
    }
}

Python

class HeapItem:
    def __init__(self, node):
        self.node = node
        self.val = node.val
    
    def __lt__(self, other):
        return self.val < other.val

class Solution:
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        heap = []
        for node in lists:
            if node is not None:
                heap.append(HeapItem(node))
        heapify(heap)
        dummy = ListNode(0)
        head = dummy
        while len(heap) != 0:
            item = heappop(heap)
            node = item.node
            head.next = node
            head = head.next
            if node.next is not None:
                heappush(heap, HeapItem(node.next))
        return dummy.next

云服务器 idc机房托管 Sorted sorted-array sorted_set merge

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

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

[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
【LeetCode Easy】021 Merge Two Sorted Lists

摘要：为减小空间复杂度，最后结果直接修改在上，不重新给分配空间。 Easy 021 Merge Two Sorted Lists Description： Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes o...

icattlecoder 2019-08-16 17:30 评论0 收藏0
[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
leetcode21 Merge Two Sorted Lists 将两个有序链表组合成一个新的有

摘要：题目要求翻译过来就是将两个有序的链表组合成一个新的有序的链表思路一循环在当前两个链表的节点都是非空的情况下比较大小，较小的添入结果链表中并且获得较小节点的下一个节点。题目要求 Merge two sorted linked lists and return it as a new list. The new list should be made by splicing togeth...

BothEyes1993 2019-08-14 18:05 评论0 收藏0
Leetcode 21 Merge Two Sorted Lists

摘要：题目详情题目要求我们将两个有序链表合成一个有序的链表。输入输出想法首先要判断其中一个链表为空的状态，这种情况直接返回另一个链表即可。每次递归都会获得当前两个链表指针位置的值较小的节点，从而组成一个新的链表。题目详情 Merge two sorted linked lists and return it as a new list. The new list should be mad...

xbynet 2019-08-14 18:01 评论0 收藏0