[LeetCode] 23. Merge k Sorted Lists

Problem : https://leetcode.com/problems/merge-k-sorted-lists/

Must divide and conquer approach to avoid exceeding time limit. 

Time Complexity = O( N log(len(lists) )

Space Complexity: O(1)

 
# 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
        """
    
        def merge(l1, l2):
            if l1 and l2:
                if l1.val < l2.val:
                    l1.next = merge(l1.next, l2)
                    return l1
                else:
                    l2.next = merge(l1, l2.next)
                    return l2
                
            return l1 if l1 else l2
        
        
        def helper(left, right):
            if left == right:
                return None
            
            if right - left == 1:
                return lists[left]
            
            if right - left == 2:
                return merge(lists[left], lists[left+1])
            
            
            mid = left + (right - left) // 2
            return merge(helper(left, mid), helper(mid, right))
    
            
        return helper(0, len(lists))

Use priority queue to merge K sorted list. N = max length of lists

Time Compleixty = O(N * Log K)

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode dummy = new ListNode();
        ListNode p = dummy;
        PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> a.val - b.val);
        for (ListNode head : lists) {
            if (head != null) pq.offer(head);
        }
        
        while (!pq.isEmpty()) {
            p.next = pq.poll();
            p = p.next;
            if (p.next != null) pq.offer(p.next);
        }

        return dummy.next;
    }
}