Merge k Sorted Lists

23 Merge k Sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Example:

Input:
[
  1->4->5,
  1->3->4,
  2->6
]
Output: 1->1->2->3->4->4->5->6

Merge K Sorted Lists

Problem Analysis

Since the lists has been sorted, we just need to compare the values of two nodes to decide which one should be put in the result first.

Algorithm Analysis

Here is a brute force solution by using merge two lists N times.

Also, we can implement this algorithm by merge sort like an algorithm. We keep splitting the nodes until it is a single node and merging them by their values.

Time Complexity Analysis

Time: O(N^2) -> O(N)

Code Implementation

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode dummy = new ListNode(0);
        for(ListNode list : lists) {
            dummy.next = mergeTwoLists(dummy.next, list);
        }
        return dummy.next;
    }
    
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        
        while(l1 != null || l2 != null) {
            if(l1 == null) {
                cur.next = l2;
                return dummy.next;
            }
            
            if(l2 == null) {
                cur.next = l1;
                return dummy.next;
            }
            
            if(l1.val < l2.val) {
                cur.next = l1;
                cur = cur.next;
                l1 = l1.next;
            }
            else {
                cur.next = l2; 
                cur = cur.next;
                l2 = l2.next;
            }
        }   
        return dummy.next;
    }
}

Code Implementation - Merge Sort

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists == null || lists.length == 0) return null;
        return merge(lists, 0, lists.length - 1);
    }
    
    public ListNode merge(ListNode[] lists, int start, int end) {
        if(start == end) {
            return lists[start];
        }
        int mid = start + (end - start) / 2;
        ListNode head1 = merge(lists, start, mid);
        ListNode head2 = merge(lists, mid + 1, end);
        return mergeSort(head1, head2);
    }
    
    public ListNode mergeSort(ListNode head1, ListNode head2) {
        if(head1 == null || head2 == null) {
            return head1 == null ? head2 : head1;
        }
        if(head1.val <= head2.val) {
            head1.next = mergeSort(head1.next, head2);
            return head1;
        } else {
            head2.next = mergeSort(head1, head2.next);
            return head2;
        } 
    }
}

Leetcode - No. 23