[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  

相关内容

热门资讯

透视脚本!wepoker手机版... 透视脚本!wepoker手机版透视脚本,wepoker辅助器免费(透视)本来是有挂1、下载好wepo...
透视软件!德扑圈透视(透视)透... 透视软件!德扑圈透视(透视)透视辅助软件下载(其实是有挂)1、德扑圈透视ai辅助优化,德扑圈透视发牌...
透视好牌!wpk可以作弊吗,(... 透视好牌!wpk可以作弊吗,(WPk)一直有挂(详细辅助)1)wpk可以作弊吗辅助挂:进一步探索wp...
透视好友!wepoker的辅助... 透视好友!wepoker的辅助器,wepoker辅助器安装包定制(透视)竟然真的是有挂1、玩家可以在...
透视免费!德普之星透视辅助软件... 透视免费!德普之星透视辅助软件激活码(透视)app安卓版破解版(本来是有挂);1、上手简单,内置详细...
透视规律!wpk官网下载链接,... 透视规律!wpk官网下载链接,(WPk)果然有挂(详细透视辅助)1、让任何用户在无需wpk官网下载链...
辅助透视!wepoker透视有... 辅助透视!wepoker透视有没有,wepoker免费脚本咨询(透视)果然是有挂;wepoker免费...
透视挂!德普之星透视软件免费入... 透视挂!德普之星透视软件免费入口官网(透视)透视(竟然真的有挂)1、金币登录送、破产送、升级送、活动...
透视中牌率!wepoker私人... 透视中牌率!wepoker私人辅助器,wepoker提高好牌率(透视)其实真的是有挂;暗藏猫腻,小编...
透视黑科技!wpk真的有透视嘛... 透视黑科技!wpk真的有透视嘛,(wpK)果然真的是有挂(详细德州局透视)wpk真的有透视嘛辅助器中...