Merge K Sorted Lists - Leetcode 23 - Python
Vložit
- čas přidán 26. 07. 2024
- 🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🐦 Twitter: / neetcode1
🥷 Discord: / discord
🐮 Support the channel: / neetcode
Coding Solutions: • Coding Interview Solut...
Solve it yourself: neetcode.io/problems/reverse-...
0:00 - Conceptual Solution
4:40 - Coding solution
#leetcode #mergesort #linkedlist
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission. - Věda a technologie
🚀 neetcode.io/ - I created a FREE site to make interview prep a lot easier, hope it helps! ❤
Rem best girl
I have a doubt on the time complexity in this question, I got log(Nklogk) as there is for loop inside while loop, Am i right? Please reply
@@tanish5662 Can you explain please? There are n linked lists in the 'lists' list and per iteration we merge two items in the list, but we iterate through all items in each element of 'lists' atleast once, so i guess it's O(n log(k))
Hi @@vijethkashyap151, its been 4 weeks and I don't remember my thought process, However I think I got this time complexity as there is a for loop inside while loop. To be precise, by just looking at the code I can say there are 3 nested loops, that might be one of the reason. If u think one of the loop is O(1), just tell me which one. I also remember asking chat gpt 4 about this and it agreed with me.
I love the way you get right into the crux of the problem rather explaining unwanted details. Cool video and keep them coming, thanks.
You are the best at simplifying problems ... Glad I found you.
Thank you Sir. Very well explained. My favorite youtube channel for python/leetcode studies.
I code in Java, but with your explanations, I do not even need to look at your code. Keep up the good work!! You make everything super simple!!
I've come up with the heap solution and I'm glad to know there's also another solution that only uses basic data structures like linked lists to solve it. Pretty amazing!!
great explanation! Very clear and concise!
You're awesome man, can't thank you enough!
Bro is a genius , breaks down hard problems into such easy solutions.
Really good explanation!
Thanks sir, These videos are very help full.
You are the legend. Thank you for your job
you explain Leetcode HARD in 5 minutes (P.S i watch in 2x). you are awesome bro. i am your fan
GENIUS PLZ DON'T STOP
I used a sorted deque (ascending) to solve this. When I used the first element, I would pop it, point at the next, then insert into the deque in the correct position based off of the new head.
This was fast enough for leetcode's judges, but I don't know how to describe the time complexity of it.
Thank you soo much for this!!
Nice solution! But you can also use heap which is much easier and more simple.
heap runs in O(knlogn) which is a lot slower than O(nlogn) which is the time complexity of the solution in the video
@@terrancejarod5187 its wrong to say O(knlogn).It would be O(nlogk)
I implemented both in Java using PriorityQueue (Heap) and the one from this video, runtime is quite similar. I think both are O(n log k)
@terrancejarod5187 First we heapify k elements which can be done in O(k). Then while heap is not empty, we pop from heap with O(lg k), advance the list and push to heap with O(lgk) if list is not none. So apart from the heapify, each node takes O(lgk) time.
Time complexity is thus O(k) + O(nlgk) where n is the total number of elements across all lists and k is the number of lists.
Thinking about an alternative:
Have a priority queue filled with the heads of the lists;
pop the smallest,
add it to the result list,
push the head of the list it originated from,
repeat.
If I am not mistaken, this should join K lists in O(n).
Inserting an element into a priority queue is O(logn). Inserting n elements would then be O(nlogn).
But seeing as you would only ever have k elements in your priority queue, you would get log k. And since you are inserting n nodes, you will get O(nlogk)
It is O(nlogk) runtime and O(k) space which is almost as good as mergesort but not O(1) space
@@Dun1007 Merge sort should be O(n) space.
Why do you need a priority queue to compare and find smallest head? It just becomes finding smallest node in list of nodes
@@calvio2835 You don't need any data structures at the end of the day. Might as well do two sum in O(n^2) time but you are definitely not going to pass an interview. How do you think we're going to find the next smallest head? Linear scan? That's inefficient given that you have to do that every single time you move a node. Priority queue is better than running a linear scan every time you pop an element.
You don't need a priority queue but since we're optimizing for time, a priority queue is superior. Why run the algorithm in O(nk) time when you could run it in O(nlogk)?
Thanks for your explanation. Can you please make a video that explains the Leetcode 632: Smallest range covering elements from K lists?
Great video! Does the mergedLists variable take up O(K) memory complexity?
get it thanks a lot!
i used a heap containing the lists and their sizes, where i pop the two least lists (in size) merge them together and insert the merged list into the heap with its new size, shouldn't this be much more efficient when the sizes of the lists varies ?
For loops for divide and conquer instead of recursion. Nice
if you implemented the merge 2 lists, we can just start merging from reverse order and remove the merged row from lists:
while len(lists) > 1:
lists[-2] = merge(lists[-1], lists[-2])
lists.pop()
return lists[0]
or this option seems better:
while len(lists) > 1:
for i in range(len(lists)//2):
lists[i] = merge(lists[i], lists[-1])
lists.pop()
return lists[0]
this implementation is simpler and it keeps the same runtime complexity (tho it runs slower in leetcode)
class Solution:
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
res = None
for l in lists:
res = merge(res, l)
return res
pretty sophisticated and enrapturing solution , and I think alternatively we could pick out minheap to sort this problem
This is clever! Is it considered a divide and conquer solution?
Thanks for the video. Very easy way to approach the problem. A minor question. Line # 17 does not work for me. I have to replace with mergeLists.append(self.mergeLists(l1, l2)). What is the difference in your way (without append) and my way ?
He fixes it to your way later on in the video. It was a mistake.
How the case of len(lists)==1 will be handled?
thank you very much, I personally think the previous LRU cache problem should be in hard category instead of this one .
btw u can simply it by using a queue. Convert the lists into a queue, and then u can simply popleft and append at the end
q=deque([l for l in lists])
while len(q)!=1:
l1=q.popleft()
l2=q.popleft()
mList=merge(l1,l2)
q.append(mList)
return q[0]
After watching your life story video I just realized this video was uploaded at your life rock bottom... But you still did a great job explaining even at that point!
4:00 n log k complexity is true because each level costs O(n) total and there are log k levels. Wouldn't choose this simple solution without realizing this math first (since there are k-1 steps, doesn't seem like n log k at first glance). So I coded a complicated n log k solution instead xD
the first if statement can just be `if not lists`...that'll check if the list is empty.
the most straighforward intuitive approach is.
just iterate through all the linked list and get their values append those values to a list.
then sort.
then just convert the combined sorted list to a linked list.
there were no restrictions so its the simplest approach.
that approach beats 80% of python submissions
your solution would be O(NK*log(NK)) time and O(NK) space where K is the # of lists and N is average length of lists. The optimal solution is O(NK*log(K)) time and O(K) space.
It's important to use big O when analyzing optimal, interviewers do not care about Leetcode submission times
I'm not sure if what you described matches the implementation. Am I correct in understanding that the implementation doesn't use a divide and conquer approach but rather merges two lists at a time and then merges the resulting list with the next list in the list of lists? From an arithmetic standpoint, it seems like the sum you're computing follows the pattern k + (k-1) + (k-2) + ... + 1, which simplifies to \( \frac{k(k+1)}{2} \). Consequently, the overall time complexity remains. O(k.n) and not O(nlog k) as with a divide and conquer strategy. Could you confirm if my understanding is correct?
I have the same doubt. I also feel it is O(kn)
It is a little difficult to see at first but it is divide and conquer. Instead of recursively splitting in half, it merges 2 together and adds the combined list to the *end* . Then takes the next 2 from the *start* of the lists.
Say you had four linked lists in lists. lists = [a, b, c, d]
Then lists would look like the following after each iteration where the result of merging a and b is ab:
[a,b,c,d]
[c,d,ab]
[ab,cd]
[abcd]
It's not:
[a,b,c,d]
[ab,c,d]
[abc,d]
[abcd]
Hope that helps!
That is pretty neat solution & explanation, beats 1.7x my minHeap solution
I don't quite understand line 18. Wouldn't it replace the original 'lists' parameter? If so, where do the rest of the lists to be merged go?
The input is a list of linked lists. Say you got 4 lists - the for loop merges 1st and 2nd together into a single linked list and apppends the head of that linked list to the merged_lists (list). Then it merges 3d and 4th together and appends the result (head of the linked list) to the merged_lists again. Now the length of the merged_list is 2 (becase you appended 2 heads). It'll now overwrite the orginal "lists" parameter (4 linked lists) with merged_lists (2 linked lists). Becuse it's greater than 1, it'll run the for loop again merging those 2 linked lists into a single one. Then again it'll overwrite the "lists" parameter (2 linked lists) with merged_lists (1 linked list). At that point the while loop (while len(lists) > 1) exits and returns the head of the linked list.
@@dtcx but why can't we create an empty list - my list = [] and then set my list = merged lists and return mylist[0]? why do we have to overwrite the input? I thought we only care about what we return? why the first doesn't work but the 2nd does?
while len(lists) > 1:
res = []
merged = []
for i in range(0, len(lists), 2):
list1 = lists[i]
if (i + 1) < len(lists):
list2 = lists[i + 1]
else:
list2 = None
merged.append(self.ml(list1, list2))
res = merged
return res[0]
vs.
while len(lists) > 1:
merged = []
for i in range(0, len(lists), 2):
list1 = lists[i]
if (i + 1) < len(lists):
list2 = lists[i + 1]
else:
list2 = None
merged.append(self.ml(list1, list2))
lists = merged
return lists[0]
funny thing about this (in python)
merge sort will not get you the fastest result.
you can traverse each listnode and add their vals to a single unsorted list. call python's (reverse) sort method on it. turn this reverse sorted list into a linkedlist, and return that. much faster.
but interviewers will prefer to see the merge sort method.
Center blew the snap, you coding style as good as the sound from your keyboard
Isn't the time complexity O(NKlgK). The first step the depth is lgK and there are k elements. So it is O(KlgK) initially. Now for every subsequent level it is O(KlgK) N/K times. Now to merge all of them together it would be O(NKlgK).
using a MinHeap would make it O(NlgK)
basically asking for a merge sort algorithm with linked lists structure rather than vectors, which is actually simpler because we don't have to allocate memory.
is this a duplicated in blind75 list?
Can we use recursion (divide and conquer) instead of the for loop to parse through the list?
I.m also having the same thought process, like using merge sort
I think it takes more memory. Correct me If I'm wrong.
it didn't come up to me that this is exactly the merge sort, even though I noticed the pattern in the two merge problem
What's the complexity of this solution?
The eastiest to understand solution with O(nlogn) time and O(n) memory complexity is to use Counter, where we store node value as key, and as value number of occurencies in all lists. Then we sort keys in counter and just generate the result.
class Solution:
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
dummy = ListNode(0)
tail = dummy
counter = Counter()
for single_list in lists:
while single_list:
counter[single_list.val] += 1
single_list = single_list.next
for key in sorted(counter.keys()):
while counter[key] > 0:
tail.next = ListNode(key)
counter[key] -= 1
tail = tail.next
return dummy.next
If you're going to sort the values, there's not really any advantage to storing them in a Counter. You can just put all the values in a Python list and sort that. LeetCode even has that as one of the solutions on their official solutions page:
class Solution:
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
self.nodes = []
head = point = ListNode(0)
for l in lists:
while l:
self.nodes.append(l.val)
l = l.next
for x in sorted(self.nodes):
point.next = ListNode(x)
point = point.next
return head.next
i think using heaps (k-way merge) would have been cleaner
I used a hashmap to kepe track of the seen values(and append after them when seen again).
I used two stacks, one for keeping smaller values than current value and other for keeping larger values than current value. I keep poping the values from one and append to another till I find the appropriate place to insert the current value.
My solution beats 92% users in runtime with 69ms. But i'm not sure if its he right approach.
class Solution:
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
head = None
hashmap = {}
stack_left = [float("-infinity")]
stack_right = [float("infinity")]
for l in lists:
curr = l
while curr:
nxt = curr.next
if curr.val in hashmap:
temp = hashmap[curr.val].next
hashmap[curr.val].next = ListNode(curr.val, temp)
curr = hashmap[curr.val].next
else:
while curr.val < stack_left[-1]:
stack_right.append(stack_left.pop())
while curr.val > stack_right[-1]:
stack_left.append(stack_right.pop())
if stack_left[-1] > float("-infinity"):
temp = hashmap[stack_left[-1]].next
hashmap[stack_left[-1]].next = ListNode(curr.val, temp)
curr = hashmap[stack_left[-1]].next
else:
head = ListNode(curr.val, head)
curr = head
stack_left.append(curr.val)
hashmap[curr.val] = curr
curr = nxt
return head
For anyone sugestiong to use heap, heres why you shouldn't:
Suppose we have n lists and each list has say k elements.
No in order to insert those values to heap, it'll take n*k*log(something). While here its less ig. Please correct me if I am wrong.
His n in O(n*k) and O(n*log(k)) is different from the heap implementation's n in O(n*k*log(k)). In the heap n, n represents the average number of elements in a single linked list, while his n represents the total number of elements in all linked lists. The time complexities are actually the same for both implementations once you account for this difference in the definition of n.
for me , an easy way to solve this problem was with a priority queue
Hii @NeetCode can u plz explain, what is the difference between 'len(lists) == 0' and 'not list'.
I'm curious about that too.
I think its 1. A empty list and 2. NULL value
It's the same. Either of them will check for empty list.
@@mindsetnuggets thanks
Hey! which keyboard do you use?
I solved this problem in like 15 minutes but was not efficient, fast but took a ton of memory. other problems that are medium and easy took me hours vs this hard problem. (im not even smart lol)
Great solution! There is a kind of a bug in your typescript solution but it technically runs anyway regardless of fixing it. For about an hour, I was wondering why it didn't work when I converted it to JavaScript. My while loop in the mergeList function had while not null for l1 and l2 instead of just while l1 and l2. It turns out that line 22 in your solution doesn't ever fire off the else statement, so l2 doesn't get set to None (or null if using another language). It runs because of the while l1 and l2 which accounts for undefined, which is what l2 could be in the case of the first test case with list of length 3. l2 gets declared but doesn't get defined because it never activates the else. Like if len of the lists was 3 and i = 2, it would be compare (2 + 1) > 3. To test it I even removed the else line and it still ran fine. You can fix it by changing it to if (i + 1) > lists.length - 1 to fix it. I would imagine this is also the case with the python solution.
Your comparison opertor should actually be "less than". e.g l2 = lists[i+1] if (i+1) < len(lists) else None. Because you want your index to be less than the length of the list. Otherwise you'll get "list out of range error"
Why do you have to return lists[0]? Could we just return mergedList?
If the original input 'lists' only had a single element we'd skip over the while loop because the condition is 'while len(lists) > 1'. In that case mergedList wouldn't be defined. But returning lists[0] would do the right thing: if there's only a single list it's by definition already merged so we can just return it.
Do #43 and #73 on the list are repeated? Both of them are 'Merge K Sorted Lists'~~
Good chatch. I guess two ways to solve the problem: Divide-and-Conquer and Heap
So between this and the heap solution, both have time complexity O(NLogK), but this solution has space complexity O(1) not counting the result as extra space while the heap solution has O(K) space where K is the number of lists. So probably better off learning this solution even though the heap one is simple and efficient, it's not optimal.
awesome
Using heaps
class Solution:
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
heap = []
for idx,element in enumerate(lists):
print(element)
if element:
heappush(heap,(element.val,idx))
dummy = curr = ListNode(0)
while heap:
val,idx = heappop(heap)
curr.next = ListNode(val)
curr = curr.next
if lists[idx].next:
lists[idx] = lists[idx].next
heappush(heap,(lists[idx].val,idx))
return dummy.next
Hello, does priority queue support compare between instances of ListNode?
@@lingyuhu4623 Nope it doesn't thats why we use the index. So for e.g lists[idx] represents the next node to add to the heap. Index 0 means that node came from first list and so on
What is n here? total number of the nodes?
Why not use a maxheap?
its a little confusing how you switch back and forth with the definition on "n". Should it be average number of elements in each list or total elements?
What's the space complexity of this?
O(1)
should be O(n) -- the mergedList array holds 2 lists (as a merged list) whose total number of elements will increase as n increases. K-way merge on a heap is O(k) in space.
Not sure about Python but it is O(1) space for C++ where you don’t have to use additional space but you just need to move the pointers
Clearly is O(n)
Pointers are also taking space bro@@charleskorey6515
The solution to this question has some other recommended solutions as well. I get that this is probably the best solution to visualize and explain, but how does it to compare to the others in runtime analysis?
Also was anyone else a lil mad when one of the recommended solutions was literally dump everything into an array and sort LOL
Not sure if it's leetcode being weird or not, but the the dump into an array and sort method performed faster for me than this video method. (video method actually didn't complete in time limit for me)
That's what I did when I first saw this problem. It feels kind of like cheating but it works and has a decent time complexity. Probably not what the interviewer is looking for though.
@@OM-el6oy The time complexity is too slow. He's hiding it for the views.
@@OM-el6oy He's using a brute force approach, and not using divide and conquer.
def mergeKLists(lists):
result = sum(lists, [])
return sorted(result)
Does anyone encounter a problem with this problem? I used the same code but it won't work in lc since the time exceeds
It still works, you just have to make sure "l2 = lists[i+1] if (i+1) < len(lists) else None" is written out correctly, if you do it another way then it won't work. Otherwise you can use the heap method.
What is space complexity of this solution ?
O(k) auxiliary space, where `k` is number of LinkedLists (from the `mergedLists` variable)
From 2023.9.24 this solution will result in TLE, I am assuming the dummy node initialization and the merging of the two lists is much more inefficient than the priority queue. Any comments?
No it doesn't fail. The code is passing all the test cases in LC 2023.12.29
Yeah it results TLE 2024.06.03
Can you also focus on the space complexity while solving a question please
why return lists[0]?
Because by the time the while loop is complete and the length of lists is equal to one, the only list in 'lists' will be the sorted one of all the ListNodes, so you can just return it (which would be the first and only element in lists -> lists[0])
@@KolydoscopeMusic thx！！
there's a linear time solution using hash map
I am having doubt, how come the time complexity is O(n log k) ? instead of O ((n*log k) log k) ?
I understood the outside (log k) part -> we are going to repeat the merge operations for log k times as the lists size halved each time. (first while loop)
But what about the inner for loop and upcoming merge operation for each pair ?
In the first while loop: my inner for loop will run k/2 times and each merge operation will cost you n times.
so it is (k/2 * n) times
In the second while loop: my inner for loop will run k/4 times and merge is n times.
so it is (k/4 * n) times
right ?
same thoughts here, @NeetCode could you please explain?
👍
divide and conquer is used to iterate on the O(nk) approach of merging one by one
for each step, `n` nodes (all of them) are compared during the merge process -- O(n)
at the end of each step, the number of lists that need to be merged has been halved
therefore the number of iterations needed is the number of times you can halve `k` until you get to 1. that is `log k` (base 2). so each step will be done `log k` times -- O(log k)
thus the time complexity is O(n log k)
what's the space complexity?
This is wrong, because each step doubles the length of n, so it scales with k.
The final merge, for instance, is two lists of about (nk / 2) size. The complexity cannot be lower than one of the steps so it has to be at least nk.
The first merges, are all n steps, but there are k/2 of them.
So that is also nk.
There are log k steps in this whole process, so the whole complexity is nk log k.
I'm curious about the space complexity in this solution, since we are creating a new list called mergedLists in the while loop, so I think we will create logK lists, so space complexity should be logK, right?
With Neetcode's implementation, mergedList is the only source of non-constant space complexity. As the length of lists (our input) increases, mergedList at its worst case stores k // 2 (O(k)) partially merged lists on the first pass of the merge step. Therefore, space complexity is O(k).
O(log(k)) is how many passes the merge step will take to make lists length 1. On each pass, the helper merge two lists method takes O(n) where n is the combined length of the two lists. Therefore, time complexity is O(n*logk).
Why is the approach showed in the video better than the following approach?
dummy = ListNode()
min_node = all_lists[0]
while len(all_lists):
i = 0
while i < len(all_lists)
if node is None:
all_lists.pop(i)
elif node.val < min_node.val:
min_node = node
i += 1
dummy.next = min_node
I don't see why it would be slower.
best
Thanks a lot for the beautiful channel, I am a big fan and love all of your solutions. In this case however I believe an easiest approach is with a min heap (that is also the category where Blind 75 put this problem in):
# O(n log k)|O(n+k) where n=total number of nodes, k=number of lists
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
heap = []
for idx, lst in enumerate(lists):
if lst:
heapq.heappush(heap, (lst.val, idx))
dummy = res = ListNode(0)
while heap:
_, idx = heapq.heappop(heap)
curr = lists[idx]
res.next = curr
if curr.next:
heapq.heappush(heap, (curr.next.val, idx))
lists[idx] = lists[idx].next
res = res.next
return dummy.next
Thanks again and keep up the great work!
space complexity is O(N) for priority queue, with merge sort you're splicing the lists together
@@konark709 what is the space complexity for the above algorithm?
U a God
I'm quite surprised you didn't use a heap :/
Whats the space complexity?
O(k), `k` is number of linked lists
auxiliary space is used in the `mergedLists` variable
Can any one explain why While len(lists)> 1 is used????
as long as your have more than one sublist in your lists input, you have to keep merging them together, so while len(lists) is not bigger than 1 meaning we have 1 or less lists, then we have our result and want to return the final list
What's the point of line 18, the one that sets "lists" equal to "mergedLists"? :
while len(lists) > 1:
mergedLists = []
for i in range(0, len(lists), 2):
l1 = lists[i]
l2 = lists[i + 1] if (i + 1) < len(lists) else None
mergedLists.append(self.mergeList(l1, l2))
lists = mergedLists
return lists[0]
You can imagine lists is [[1],[2],[3],[4],[5],[6]],after first mergeList, the mergedLists becomes[[1,2],[3,4],[5,6]],then let this mergedLists become Lists again, so the “while len(Lists)>1:” is true again and you start a new loop, and then you do it again becomes[[1,2,3,4],[5,6]], then finally the List becomes[[1,2,3,4,5,6]],return Lists[0]
I was so confused by this because I didn't realize the number 2 in "for I in range" line meant how much to increment by and not that the range of i was only from 0 to 2 😭 I was like why is the for loop only executing once
@@evynsrefuge for I in range(starting, uptonotinaluding, stepsize):
How come this one is considered as a divide and conquer ? can't wrap my head around
We have k lists and we group them into k/2 pairs, then merge each pair. Now we have k/2 lists and we merged that into k/4 pairs. So we are dividing the number of lists in half each time.
E.g. Say we have four lists. Merge list 1 and list 2 together, and merge list 3 and list 4 together. That gives us two merged lists. Now merge those two into a single result.
Fab
i cant understand why it is nlogk not n*k
See, in each iteration we are traversing all the node and the total number of iterations is logk, that's why
Can I have the same question solution in Java?
I really question the runtime analysis here.
I think time complexity of 1st solution should be O(n2k) and for optimized solution O(nlognk).
where n is size of array , k size of list.
if I am wrong plz somebody help.
Thanks in advance.
Similar code using 'heapq' and iterators
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
def l_iter(self):
_iter = self
while _iter:
yield _iter.val
_iter = _iter.next
ListNode.__iter__ = l_iter
filtered_lists = filter(lambda x: x is not None, lists)
list_head = list_tail = None
counter = count(0)
stack = []
for l in filtered_lists:
itr = iter(l)
heapq.heappush(stack, (next(itr), next(counter), itr))
while stack:
try:
val, _, itr = heapq.heappop(stack)
if not list_head:
list_head = list_tail = ListNode(val)
else:
list_tail.next = ListNode(val)
list_tail = list_tail.next
heapq.heappush(stack, (next(itr), next(counter), itr))
except:
pass
return list_head
hey
learn leetcode in here to beat 100 liked question
Anyone getting type error for this solution
im getting index out of range error for l1 even though its only while len lists > 1 idk
Such a waste explantation.
did u purposely pick those numbers to add up to 23?
This is a naive solution
divide and conquer + recursive
class Solution:
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
def mergeTwo(list1,list2):
if not list1:
return list2
if not list2:
return list1
if list1.val > list2.val:
list2.next = mergeTwo(list1,list2.next)
return list2
else:
list1.next = mergeTwo(list1.next,list2)
return list1
def divideAndConquer(l):
if len(l) == 0:
return None
if len(l) == 1:
return l[0]
return mergeTwo(divideAndConquer(l[0:(len(l) + 1) // 2]),divideAndConquer(l[(len(l) + 1) // 2:]))
return divideAndConquer(lists)
why can we do this?
@classmethod
def merge_k_sorted_list(cls, list_of_sorted_list):
if not list_of_sorted_list:
return
while len(list_of_sorted_list) > 1:
list_of_sorted_list.append(cls.merge_sorted_list(list_of_sorted_list.pop(), list_of_sorted_list.pop()))
return list_of_sorted_list[0]