Merge k Sorted Lists Solution - The Coding Shala

Home >> Interview Prep >> Merge k Sorted Lists

 In this post, we will learn how to solve the Merge k Sorted Lists problem and will implement its solution in Java.

Merge k Sorted Lists Problem

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order. Merge all the linked-lists into one sorted linked-list and return it.

Example 1:
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

Merge k Sorted Lists Solution

Approach 1

We can use an additional array to store all the elements from lists and then will sort this array. From the sorted array, we can make the linked list again.

Time Complexity: O(n logn)
Space Complexity: O(N)

Java Program: 

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0) return null;
        if (lists.length == 1) return lists[0];
        
        List<Integer> list = new ArrayList<>();
        
        for (ListNode head : lists) {
            while (head != null) {
                list.add(head.val);
                head = head.next;
            }
        }
        
        Collections.sort(list);
        if(list.size() == 0) return null; 
        ListNode head = new ListNode(list.get(0));
        ListNode temp = head;
        for (int i = 1; i < list.size(); i++) {
            ListNode newNode = new ListNode(list.get(i));
            temp.next = newNode;
            temp = temp.next;
        }
        
        return head;
    }
}

Approach 2

Using Recursion and Divide and Conquer approach. We know how to merge two lists and by using a similar approach we will solve this problem.

Read Merge two lists problem Here.

Time Complexity: O(n logn)
Space Complexity: O(1)

Java Program: 

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists.length == 0) return null;
        return divide(lists, 0, lists.length - 1);
    }
    
    // divide here
    ListNode divide(ListNode[] lists, int start, int end) {
        // base condition
        if (start == end) {
            return lists[start];
        }
        
        int mid = start + (end - start) / 2;
        ListNode l1 = divide(lists, start, mid);
        ListNode l2 = divide(lists, mid+1, end);
        
        return merge(l1, l2);
    }
    
    // merge here
    ListNode merge(ListNode l1, ListNode l2) {
        if(l1 == null) return l2;
        if(l2 == null) return l1;
        if(l1.val < l2.val) {
            l1.next = merge(l1.next, l2);
            return l1;
        } else {
            l2.next = merge(l1, l2.next);
            return l2;
        }
    }
}


Other Posts You May Like
Please leave a comment below if you like this post or found some errors, it will help me to improve my content.

Comments

Popular Posts from this Blog

Anti Diagonals - The Coding Shala

Shell Script to find sum, product and average of given numbers - The Coding Shala

LeetCode - Bulb Switcher Solution - The Coding Shala

New Year Chaos Solution - The Coding Shala

Sorting the Sentence LeetCode Solution - The Coding Shala