[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  

相关内容

热门资讯

3分钟科普!全民雀神麻将助赢神... 3分钟科普!全民雀神麻将助赢神器,德州都是真的有挂,安装教程(有挂辅助)1、全新机制【全民雀神麻将助...
8分钟实锤!东游麻将暗藏猫腻,... 8分钟实锤!东游麻将暗藏猫腻,扑克时间原来有挂,详细教程(有挂脚本)1、玩家可以在东游麻将暗藏猫腻软...
八分钟攻略!旺旺福建麻将有脚本... 八分钟攻略!旺旺福建麻将有脚本吗,AaPOKER原来存在有挂,技巧教程(有挂技巧);1、打开软件启动...
九分钟普及!南通长牌算胡牌方法... 九分钟普及!南通长牌算胡牌方法,governorofpoker3原来真的有挂,详细教程(有挂ai代打...
十分钟辅助!潮汕暗宝可以作假吗... 十分钟辅助!潮汕暗宝可以作假吗,wepoKe一直有挂,揭秘教程(有挂神器)1、许多玩家不知道潮汕暗宝...
三分钟科普!贵阳手机天天麻将a... 三分钟科普!贵阳手机天天麻将app辅牌器购买,德州app竟然真的有挂,安装教程(有挂软件)一、贵阳手...
9分钟普及!小程序的雀神麻将怎... 9分钟普及!小程序的雀神麻将怎么玩才会赢,we-poker一直是真的有挂,科技教程(有挂黑科技)1、...
九分钟辅助挂!欢乐贰柒拾有辅助... 九分钟辅助挂!欢乐贰柒拾有辅助吗,WepokE确实真的有挂,揭秘攻略(有挂秘籍);1、欢乐贰柒拾有辅...
两分钟辅助!黄冈麻将有挂吗,x... 两分钟辅助!黄冈麻将有挂吗,x-poker竟然有挂,攻略方法(有挂普及)1、该软件可以轻松地帮助玩家...
5分钟实锤!碧海麻将是不是有挂... 5分钟实锤!碧海麻将是不是有挂的,WPk一直真的是有挂,总结教程(有挂解说)1、这是跨平台的碧海麻将...