[NeetCode 150] Merge K Sorted Linked Lists
创始人
2025-01-10 17:04:35
0

Merge K Sorted Linked Lists

You are given an array of k linked lists lists, where each list is sorted in ascending order.

Return the sorted linked list that is the result of merging all of the individual linked lists.

Example 1:

Input: lists = [[1,2,4],[1,3,5],[3,6]]  Output: [1,1,2,3,3,4,5,6] 

Example 2:

Input: lists = []  Output: [] 

Example 3:

Input: lists = [[]]  Output: [] 

Constraints:

0 <= lists.length <= 1000 0 <= lists[i].length <= 100 -1000 <= lists[i][j] <= 1000 

Solution

To take advantage of the feature that each list is sorted in ascending order, it is OK to use O ( number of elements in 2 lists ) O(\text{number of elements in 2 lists}) O(number of elements in 2 lists) two pointers method to merge 2 ordered lists. The overall time complexity will be O ( number of all elements × number of linked lists ) O(\text{number of all elements}\times \text{number of linked lists}) O(number of all elements×number of linked lists).

We can accelerate this process by a simple priority queue, reducing the time complexity to O ( n log ⁡ n ) O(n\log n) O(nlogn), where n n n denotes the total number of all elements in linked lists.

However, by using hash, or bucket sort, wo can achieve O ( V ) O(V) O(V) time complexity, where V V V denotes the size of the discrete value domain of elements, and V ≤ n V\le n V≤n. Additionally, it does not require the given linked lists to be ordered.

To be more detailed, we can use a dictionary to store the nodes of different values and link them together in the end. The code might look like:

# Definition for singly-linked list. # class ListNode: #     def __init__(self, val=0, next=None): #         self.val = val #         self.next = next  class Solution:         def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:         buket = {number:None for number in range(-1000, 1001)}         for node in lists:             while node.next:                 buket[node.val].append(node)                 node = node.next             buket[node.val].append(node)         preNode = None         rootNode = None         for value in buket.values():             for node in value:                 if preNode:                     preNode.next = node                 else:                     rootNode = node                 preNode = node         return rootNode 

However, that is not perfect! As the elements are all stored in linked lists, we only need to store the head and tail nodes of each value. When a new element coming in, we just link it as the new head/tail. In the end, we only need to link head and tail of different values’ linked list one by one. This method only takes O ( V ) O(V) O(V) extra space and O ( V ) O(V) O(V) time to link.

Code

Please ignore the typo of “bucket”.

# Definition for singly-linked list. # class ListNode: #     def __init__(self, val=0, next=None): #         self.val = val #         self.next = next  class Solution:         def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:         head_buket = {}         tail_buket = {}         for node in lists:             while True:                 if node.val not in tail_buket:                     tail_buket[node.val] = node                 nextNode = node.next                 node.next = head_buket.get(node.val, None)                 head_buket[node.val] = node                 node = nextNode                 if node is None:                     break         preNode = None         rootNode = None         for key in range(-1000, 1001):             if key in head_buket:                 if preNode is None:                     rootNode = head_buket[key]                 else:                     preNode.next = head_buket[key]                 preNode = tail_buket[key]          return rootNode  

相关内容

热门资讯

透视智能ai(wepoker)... 透视智能ai(wepoker)wepoker祈福有用吗(透视)一贯真的有挂(新版2025教程)1、很...
透视数据!如何下载wepoke... 透视数据!如何下载wepoker安装包,真是有挂(透视)力荐教程(有挂插件);1.如何下载wepok...
透视ai!aapoker破解侠... 透视ai!aapoker破解侠是真的吗(透视)透视插件(一贯是有挂)1、让任何用户在无需aapoke...
透视好友房"如何下载... 透视好友房"如何下载wpk透视版"一贯真的有挂(透视)力荐教程(有挂脚本);1、如何下载wpk透视版...
透视讲解(WEPOKER)we... 透视讲解(WEPOKER)wepoker私人局俱乐部(透视)一贯真的是有挂(教你攻略)1、构建自己的...
透视最新!aapoker透视脚... 透视最新!aapoker透视脚本下载(透视)透视脚本下载(竟然是真的有挂);1、aapoker透视脚...
透视ai代打!wepoker模... 透视ai代打!wepoker模拟器哪个好用,固有是有挂(透视)2025新版总结(有挂辅助)1、这是跨...
透视ai"如何下载w... 透视ai"如何下载wepoker安装包"确实真的有挂(透视)AI教程(有挂方法)1、金币登录送、破产...
透视ai(wepoker)we... 透视ai(wepoker)wepoker透视有用吗(透视)一贯存在有挂(微扑克教程)1、wepoke...
透视app!aapoker透视... 透视app!aapoker透视脚本(透视)真的假的(原来真的是有挂)1、完成aapoker透视脚本的...