23. 合并K个排序链表

yuanran0 2020-01-30

合并 个排序链表,返回合并后的排序链表。请分析和描述算法的复杂度。

本题我掌握了两个方法:

1. 遍历所有链表,将其 nodes 的 val 放入一个list, 然后list.sort(),然后再放入链表result   O(NlogN)

2. 就是我用的方法,先写合并两个链表的函数,再分而治之的合并 O(NlogK)

收获:

1.掌握了定义一个新链表的方法:(终于掌握了,前几天百度了好久)

  给定 vals 输入 nums (List)

  head = point = ListNode(0)

  for i in range(len(nums)):

    point.next = ListNode(nums[i])

    point = point.next

  return head.next

2.体会了一下分治,估计还不太够,还需要写几道这样的题才能掌握。

    

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

class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        if not lists: return
        length = len(lists)
        interval = 1
        while interval < length:
            for i in range(0,length - interval,interval*2):
                lists[i] = self.merge2Lists(lists[i],lists[i+interval])
            interval *=2
        return lists[0] if length>0 else lists

    def merge2Lists(self,list1,list2):
        head = point = ListNode(0)
        while list1 and list2:
            if list1.val < list2.val:
                point.next  =list1
                list1 = list1.next
                point = point.next
            else:
                point.next = list2
                list2 = list2.next
                point = point.next
        if not list1:
            point.next = list2
        if not list2:
            point.next = list1
        return head.next 

相关推荐