Merge K sorted list

Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked-lists are:
[
1->4->5,
1->3->4,
2->6
]
merging them into one sorted list:
1->1->2->3->4->4->5->6
Input: lists = []
Output: []
Input: lists = [[]]
Output: []
  • k == lists.length
  • 0 <= k <= 10^4
  • 0 <= lists[i].length <= 500
  • -10^4 <= lists[i][j] <= 10^4
  • lists[i] is sorted in ascending order.
  • The sum of lists[i].length won't exceed 10^4.

class Solution:
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
inter=[]
for i in lists:
if i!=None:
inter.append(i)
dummy=ListNode(0)
temp=dummy
while(inter):
i=0
mini_val=float('inf')
while(i<len(inter)):
if inter[i].val<=mini_val:
mini_ind=i
mini_val=inter[i].val
i+=1
temp.next=inter[mini_ind]
temp=temp.next
inter[mini_ind]=inter[mini_ind].next
if(inter[mini_ind]==None):
inter.pop(mini_ind)
temp.next=None
return dummy.next
import heapq as hq 
class Solution:
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
dummy=ListNode(0)
temp=dummy
heap=[]

for i in lists:
head=i
while(head):
heap.append(head.val)
head=head.next

hq.heapify(heap)
while(heap):
temp.next=ListNode(hq.heappop(heap))
temp=temp.next
return dummy.next

--

--

--

Tech-Enthusiast, Coder,Explorer,Geeky,Software Engineer |A piece of code delivers everything that you need. The world is all about codes.

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Fundraising News|NFT-Fi Hub Platform 0xAdventure invested by 10 Top Tier Guilds!

Bonjour Web 3.0!

Java Apache Arrow: Read and Write to a ListVector

A Level H2 Computing

“My 40 days journey to the Kubernetes Trifecta”

Serving a Static Site Over HTTPS Using S3, CloudFront, and GoDaddy

Powerlevel9k Themes

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Dhanarajappu

Dhanarajappu

Tech-Enthusiast, Coder,Explorer,Geeky,Software Engineer |A piece of code delivers everything that you need. The world is all about codes.

More from Medium

Joy of Computer Program's Logic

Competitive Programming Grader For All Programmers

[LeetCode]#2089. Find Target Indices After Sorting Array

Big O Notation - 1