【LeetCode每天一题】 Merge k Sorted Lists(合并K个有序链表)

桃扇骨 2021-12-15 14:21 229阅读 0赞

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
    
    思路

--------------------

这道题最简单的方法就是我们将K个链表中的所有数据都存进数组中，然后对数据进行排序。排序完毕之后在依此对数组中的数据进行链表的构造。时间复杂度为O(n log n),n 是链表元素的总和。

第二种思路是我们我们可以将列表中两个链表两个链表进行合并，直到最后合并完只剩下一条链表，就是排序之后的链表。时间复杂度为O(Nlog k)(N是总的元素数)，空间复杂度为O(1)。
    第二种图示

--------------------

第一种方法的解决代码

--------------------

1 class Solution(object):
     2     def mergeKLists(self, lists):
     3         """
     4         :type lists: List[ListNode]
     5         :rtype: ListNode
     6         """
     7         self.nodes = []
     8         head = point = ListNode(0)    # 设置哨兵节点
     9         for l in lists:                  # 循环遍历列表中每一个链表，将元素添加进数组。
    10             while l:                     # 将当前链表中的元素进行添加
    11                 self.nodes.append(l.val)
    12                 l = l.next
    13         for x in sorted(self.nodes):          # 将排序之后的数组中的元素，构造链表。
    14             point.next = ListNode(x)
    15             point = point.next
    16         return head.next

第二种方法的解决代码

--------------------

1 class Solution(object):
     2     def mergeKLists(self, lists):
     3         """
     4         :type lists: List[ListNode]
     5         :rtype: ListNode
     6         """
     7         amount = len(lists)          # 计算出K的数值
     8         interval = 1                        # 间距
     9         while interval < amount:    # 先从间距1开始合并，
    10             for i in range(0, amount - interval, interval * 2): 
    11                 lists[i] = self.merge2Lists(lists[i], lists[i + interval])   # 使用两个链表的合并函数进行合并。
    12             interval *= 2        # 当上一次间距合并完之后，将间距扩大为2倍。
    13         return lists[0] if amount > 0 else lists      # 当列表链表数大于0时，返回第一个链表（排序好的链表）。
    14  
    15     def merge2Lists(self, l1, l2):         # 两个链表进行合并成一个链表。
    16         head = point = ListNode(0)       # 设置哨兵节点
    17         while l1 and l2:
    18             if l1.val <= l2.val:
    19                 point.next = l1
    20                 l1 = l1.next
    21             else:
    22                 point.next = l2
    23                 l2 = l1
    24                 l1 = point.next.next
    25             point = point.next
    26         if not l1:                            #  其中一个链表不为空，就将其添加到后面。
    27             point.next=l2
    28         else:
    29             point.next=l1
    30         return head.next

转载于:https://www.cnblogs.com/GoodRnne/p/10662223.html