[LeetCode] Merge k Sorted Lists

 

 

Problem

 

 

---

 

Solution

 

My initial approach was to compare the head nodes from each list, put the smallest onto the result linked list, and proceed the pointer that was on the smallest node. The time complexity for this approach would be O(kN) where k is the number of elements in lists and N is the number of nodes in the final linked list. I did not find a clean way to implement this.

 

Solution using merge sort:

Divide the given lists into smaller lists of linked lists with recursion.

Merge the divided lists two halves at a time by going through both linked lists and putting the elements in order. Do this recursively until there is one linked list with every element in sorted order.

 

Time Complexity

O(M logN) where N is the length of the lists argument and M is the size of the merged linked list. 

 

 

Space Complexity

O(logN)?

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        if not lists:
        	return None
        if len(lists) == 1:
        	return lists[0]
        
        mid = len(lists)//2
        left = self.mergeKLists(lists[:mid])
        right = self.mergeKLists(lists[mid:])
        return self.merge(left, right)
        
    def merge(self, l, r):
    	root = curr = ListNode(0)
        while l and r:
        	if l.val < r.val:
            	curr.next = l
                l = l.next
            else:
            	curr.next = r
                r = r.next
            curr = curr.next
        
        curr.next = l or r
        return root.next