合并 k 个排序链表, 返回合并后的排序链表. 请分析和描述算法的复杂度.
本题我掌握了两个方法:
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
来源: http://www.bubuko.com/infodetail-3399919.html