[Leetcode] Merge Two Sorted Lists Merge K Sorted L

stefanieliang 發布于2019-08-14 12:30 / 2995人閱讀

摘要：注意因為堆中是鏈表節點，我們在初始化堆時還要新建一個的類。代碼初始化大小為的堆拿出堆頂元素將堆頂元素的下一個加入堆中

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

云服務器 GPU云服務器 Sorted sorted-array sorted_set merge

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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