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

• Remove Duplicates from Sorted Linked List
• Sort a Linked List Using Insertion Sort
• Flatten a Multilevel Doubly Linked List
• Merge Two Sorted Linked Lists
• Remove Linked List Elements

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