[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代打);所有人都在...
一分钟揭秘!微扑克辅助软件(透... 一分钟揭秘!微扑克辅助软件(透视辅助)确实是有挂(2024已更新)(哔哩哔哩);1、用户打开应用后不...
五分钟发现!广东雀神麻雀怎么赢... 五分钟发现!广东雀神麻雀怎么赢,朋朋棋牌都是是真的有挂,高科技教程(有挂方法)1、广东雀神麻雀怎么赢...
每日必看!人皇大厅吗(透明挂)... 每日必看!人皇大厅吗(透明挂)好像存在有挂(2026已更新)(哔哩哔哩);人皇大厅吗辅助器中分为三种...
重大科普!新华棋牌有挂吗(透视... 重大科普!新华棋牌有挂吗(透视)一直是有挂(2021已更新)(哔哩哔哩)1、完成新华棋牌有挂吗的残局...
二分钟内幕!微信小程序途游辅助... 二分钟内幕!微信小程序途游辅助器,掌中乐游戏中心其实存在有挂,微扑克教程(有挂规律)二分钟内幕!微信...
科技揭秘!jj斗地主系统控牌吗... 科技揭秘!jj斗地主系统控牌吗(透视)本来真的是有挂(2025已更新)(哔哩哔哩)1、科技揭秘!jj...
1分钟普及!哈灵麻将攻略小,微... 1分钟普及!哈灵麻将攻略小,微信小程序十三张好像存在有挂,规律教程(有挂技巧)哈灵麻将攻略小是一种具...
9分钟教程!科乐麻将有挂吗,传... 9分钟教程!科乐麻将有挂吗,传送屋高防版辅助(总是存在有挂)1、完成传送屋高防版辅助透视辅助安装,帮...
每日必看教程!兴动游戏辅助器下... 每日必看教程!兴动游戏辅助器下载(辅助)真是真的有挂(2025已更新)(哔哩哔哩)1、打开软件启动之...