[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  

相关内容

热门资讯

2024新版教程!wpk辅助透... 2024新版教程!wpk辅助透视(德扑数据软件)其实真的有挂(详细透明挂教程)1、德扑数据软件系统规...
AI辅助!德扑之星刷数据(透视... AI辅助!德扑之星刷数据(透视)外挂透明挂辅助器安装(有挂存在)-哔哩哔哩1、让任何用户在无需AI插...
教你攻略!德州ai辅助器(德扑... 教你攻略!德州ai辅助器(德扑ai助手)其实真的是有挂(详细透视辅助教程)教你攻略!德州ai辅助器(...
教你攻略辅助!德扑数据分析软件... 教你攻略辅助!德扑数据分析软件(透明)外挂透明挂辅助app(有挂工具)-哔哩哔哩1、德扑数据分析软件...
wpk教程!wpk微扑克有辅助... wpk教程!wpk微扑克有辅助吗(wepoke模拟器)原来确实真的有挂(详细透视辅助教程)1、这是跨...
2024新版总结辅助!德州辅助... 2024新版总结辅助!德州辅助软件线上(透视)外挂透明挂辅助插件(真的有挂)-哔哩哔哩1、下载好德州...
透明挂教程!wepoke软件收... 透明挂教程!wepoke软件收费是真的吗(德州之星辅助)原来真的是有挂(详细辅助挂教程)1)wepo...
2024新版技巧辅助!wepo... 2024新版技巧辅助!wepoke游戏数据有说法吗(透视)外挂透明挂辅助器安装(有挂详情)-哔哩哔哩...
技巧教程!pokerworld... 技巧教程!pokerworld下载(WPK透视辅助)原来真的有挂(详细透明挂教程);1分钟了解详细教...
德州论坛辅助!wpk外挂被实锤... 德州论坛辅助!wpk外挂被实锤(透明)外挂透明挂辅助app(有挂分析)-哔哩哔哩是一款可以让一直输的...