Powered by GitBook

Merge k Sorted Lists

Question

leetcode: Merge k Sorted Lists | LeetCode OJ
lintcode: (104) Merge k Sorted Lists

题解1 - 选择归并(TLE)

参考 Merge Two Sorted Lists | Data Structure and Algorithm 中对两个有序链表的合并方法，这里我们也可以采用从 k 个链表中选择其中最小值的节点链接到lastNode->next(和选择排序思路有点类似)，同时该节点所在的链表表头节点往后递推一个。直至lastNode遍历完 k 个链表的所有节点，此时表头节点均为NULL, 返回dummy->next.

这种方法非常简单直接，但是时间复杂度较高，容易出现 TLE.

题解2 - 迭代调用`Merge Two Sorted Lists`(TLE)

鉴于题解1时间复杂度较高，题解2中我们可以反复利用时间复杂度相对较低的 Merge Two Sorted Lists | Data Structure and Algorithm. 即先合并链表1和2，接着将合并后的新链表再与链表3合并，如此反复直至 vector 内所有链表均已完全合并^soulmachine。

题解3 - 二分调用`Merge Two Sorted Lists`

题解2中merge2Lists优化空间不大，那咱们就来看看mergeKLists中的for循环，仔细观察可得知第i个链表 $$li$$ 被遍历了 $$k-i$$ 次，如果我们使用二分法对其进行归并呢？从中间索引处进行二分归并后，每个链表参与合并的次数变为 $$\log k$$, 故总的时间复杂度可降至 $$\log k \cdot \sum {i=1} ^{k} l_i$$. 优化幅度较大。

reference
用二分的思想，就是把 Lists 分为两部分，分别递归 Merge k Sorted Lists 后变成两个 List ，然后再对这两 List 进行 Merge Two Sorted Lists 。

"""
Definition of ListNode
class ListNode(object):

    def __init__(self, val, next=None):
        self.val = val
        self.next = next
"""


class Solution:
    """
    @param lists: a list of ListNode
    @return: The head of one sorted list.
    """

    def mergeKLists(self, lists):
        if len(lists) == 0:
            return None
        if len(lists) == 1:
            return lists[0]

        mid = len(lists) // 2
        left = self.mergeKLists(lists[:mid])
        right = self.mergeKLists(lists[mid:])

        # merge left and right
        dummy = ListNode(0)
        cur = dummy
        while left or right:
            if right == None or (left and left.val <= right.val):
                cur.next = left
                left = left.next
            else:
                cur.next = right
                right = right.next
            cur = cur.next

        return dummy.next

reference
归并k个已经排好序的链表。使用堆这一数据结构，首先将每条链表的头节点进入堆中，然后将最小的弹出，并将最小的节点这条链表的下一个节点入堆，依次类推，最终形成的链表就是归并好的链表。
reference

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    # @param a list of ListNode
    # @return a ListNode
    def mergeKLists(self, lists):
        heap = []
        for node in lists:
            if node: 
                heap.append((node.val, node))
        heapq.heapify(heap)
        head = ListNode(0); curr = head
        while heap:
            pop = heapq.heappop(heap)
            curr.next = ListNode(pop[0])
            curr = curr.next
            if pop[1].next: 
                heapq.heappush(heap, (pop[1].next.val, pop[1].next))
        return head.next

reference
使用了堆

"""
Definition of ListNode
class ListNode(object):

    def __init__(self, val, next=None):
        self.val = val
        self.next = next
"""
class Solution:
    """
    @param lists: a list of ListNode
    @return: The head of one sorted list.
    """
    def mergeKLists(self, lists):
        # write your code here
        self.heap = [[i, lists[i].val] for i in range(len(lists)) if lists[i] != None]
        self.hsize = len(self.heap)
        for i in range(self.hsize - 1, -1, -1):
            self.adjustdown(i)
        nHead = ListNode(0)
        head = nHead
        while self.hsize > 0:
            ind, val = self.heap[0][0], self.heap[0][1]
            head.next = lists[ind]
            head = head.next
            lists[ind] = lists[ind].next
            if lists[ind] is None:
                self.heap[0] = self.heap[self.hsize-1]
                self.hsize = self.hsize - 1
            else:
                self.heap[0] = [ind, lists[ind].val]
            self.adjustdown(0)
        return nHead.next

    def adjustdown(self, p):
        lc = lambda x: (x + 1) * 2 - 1
        rc = lambda x: (x + 1) * 2
        while True:
            np, pv = p, self.heap[p][1]
            if lc(p) < self.hsize and self.heap[lc(p)][1] < pv:
                np, pv = lc(p), self.heap[lc(p)][1]
            if rc(p) < self.hsize and self.heap[rc(p)][1] < pv:
                np = rc(p)
            if np == p:
                break
            else:
                self.heap[np], self.heap[p] = self.heap[p], self.heap[np]
                p = np

results matching ""

No results matching ""