Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Input:
[
  1->4->5,
  1->3->4,
  2->6
]
Output: 1->1->2->3->4->4->5->6

方法1-暴力破解

只管的思路就是把每个链表上的值,放到一个数据上去,然后进行排序, 最后再生成一个新的列表

class ListNode(object):
    def __init__(self, val):
        self.val = val
        self.next = None

class Solution(object):
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        self.nodes = []
        head = point = ListNode(0)
        for l in lists:
            while l:
                self.nodes.append(l.val)
                l = l.next
        for x in sorted(self.nodes):
            point.next = ListNode(x)
            point = point.next
        return head.next
    复杂度分析:
  • 时间复杂度:O(NlgN), N代表的是总的节点数
  • (1) 重新整合所有节点耗时O(N) (2) 重新排序耗时O(NlgN) (3) 迭代生成新的链表耗时O(N)
  • 空间复杂度: O(N)
  • (1) 排序的过程需要额外的O(N)空间(取决于你选用的排序算法) (2) 生成新的链表需要空间O(N)

一个一个比较

思路: 每次拿出来k个list的第一个元素进行比较,选出最小的那个,然后不断的迭代。

  • 时间复杂度:
  • k个元素选出最小的需要k次比较,每个元素都要在k个元素里面参与一下计算,整体的时间复杂度O(nk)
class ListNode(object):
    def __init__(self, val):
        self.val = val
        self.next = None

class Solution(object):
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        dumy = ListNode(0)
        head = dumy
        while True:
            k_list = []
            for index, item in enumerate(lists):
                if item is None:
                    continue
                k_list.append((index, item.val))

            if not k_list:
                return dumy.next

            min_index, min_num = self.min_num(k_list)
            head.next = lists[min_index]
            head = head.next
            lists[min_index] = lists[min_index].next

    def min_num(self, li):
        min_index, min_num = 0, 0x8fffffff
        for index, item in li:
            if item < min_num:
                min_index = index
                min_num = item
        return min_index, min_num

此方法oj的时候回超时。

使用最小堆

维护一个大小为k的最小堆,每次进行数据插入的时间的复杂度是lg(k), 总共需要插入的次数是O(nlgk)

from queue import PriorityQueue
class Solution2(object):
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        dumy = ListNode(0)
        head = dumy
        q = PriorityQueue()
        for i in lists:
            if i:
                q.put((i.val, i))
        while not q.empty():
            min_num, node = q.get()
            head.next = node
            head = head.next
            if node.next:
                q.put((node.next.val, node.next))
        return dumy.next
/**
 * Definition for singly-linked list.
 * class ListNode(var _x: Int = 0) {
 *   var next: ListNode = null
 *   var x: Int = _x
 * }
 */

object Solution {
     def mergeKLists(lists: Array[ListNode]): ListNode = {
    val pq = mutable.PriorityQueue.empty[ListNode](Ordering.by(n => n.x)).reverse
    val dummyNode = new ListNode(0)
    var head = dummyNode

    //Insert the heads of all list nodes into the priorit yqueue
    lists.foreach(l => if(l!=null)pq.enqueue(l))

    while(!pq.isEmpty) {
      val node = pq.dequeue()
      head.next = new ListNode(node.x)
      if(node.next!=null)
      pq.enqueue(node.next)
      head = head.next
    }
  dummyNode.next
  }
}


Merge lists one by one

时间复杂度:O(kN)

Merge with Divide And Conquer

时间复杂度:O(Nlgk)