[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更新快且高清...
每日必看!智星德州菠萝外挂检测... 每日必看!智星德州菠萝外挂检测(辅助挂)软件透明挂(有挂教学)-哔哩哔哩1、玩家可以在智星德州菠萝外...
透视透明挂!轰趴十三水有后台(... 轰趴十三水有后台赢率提升策略‌;透视透明挂!轰趴十三水有后台(辅助挂)软件透明挂(有挂详情)-哔哩哔...
发现玩家!德扑ai助手软件(辅... 发现玩家!德扑ai助手软件(辅助挂)透视辅助(有挂教学)-哔哩哔哩;玩家在德扑ai助手软件中需先进行...
一分钟了解!x-poker辅助... 一分钟了解!x-poker辅助软件(辅助挂)辅助透视(有挂攻略)-哔哩哔哩1、每一步都需要思考,不同...
一分钟揭秘!德州最新辅助器(辅... 一分钟揭秘!德州最新辅助器(辅助挂)透视辅助(有挂攻略)-哔哩哔哩;德州最新辅助器最新版本免费下载安...
玩家攻略推荐!德州辅助(辅助挂... 玩家攻略推荐!德州辅助(辅助挂)辅助透视(有挂了解)-哔哩哔哩是由北京得德州辅助黑科技有限公司精心研...
揭秘真相!pokernow德州... 《揭秘真相!pokernow德州(辅助挂)辅助透视(有挂介绍)-哔哩哔哩》 pokernow德州软件...
五分钟了解!德州之星辅助器(辅... 五分钟了解!德州之星辅助器(辅助挂)辅助透视(有挂透明)-哔哩哔哩1、很好的工具软件,可以解锁游戏的...
推荐一款!pokermaste... 1、推荐一款!pokermaster有外挂(辅助挂)透视辅助(有挂教学)-哔哩哔哩;详细教程。2、p...