Solving Merge k Sorted Lists

To see the question, click here.

Naive Approach

The idea is to store all the values of the list nodes in an array, sort them using the Arrays.sort method, and then construct the linked list to return it as the answer.

// TC: O(nlogn)
// SC: O(n)

import java.util.Arrays;

class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

public class MergekSortedLists {
    public ListNode mergeKLists(ListNode[] lists) {
        int len = 0;
        for (int i = 0; i < lists.length; i++) {
            ListNode temp = lists[i];
            while (temp != null) {
                len++;
                temp = temp.next;
            }
        }

        if (len == 0) {
            return null;
        }

        int[] fin = new int[len];

        int j = 0;
        for (int i = 0; i < lists.length; i++) {
            ListNode temp = lists[i];
            while (temp != null) {
                fin[j] = temp.val;
                temp = temp.next;
                j++;
            }
        }

        Arrays.sort(fin);

        ListNode head = new ListNode(fin[0]);
        ListNode temp = head;
        for (int i = 1; i < fin.length; i++) {
            temp.next = new ListNode(fin[i]);
            temp = temp.next;
        }

        return head;
    }

    public static void main(String args[]) {
        MergekSortedLists mksl = new MergekSortedLists();
        ListNode l1 = new ListNode(1, new ListNode(4, new ListNode(5)));
        ListNode l2 = new ListNode(1, new ListNode(3, new ListNode(4)));
        ListNode l3 = new ListNode(2, new ListNode(6));
        ListNode[] lists = { l1, l2, l3 };
        ListNode head = mksl.mergeKLists(lists);
        while (head != null) {
            System.out.print(head.val + " ");
            head = head.next;
        }
    }
}

Performance

The time complexity of the mergeKLists method is O(nlogn). This is because we are iterating over all the nodes in the input lists to create a single array of values, which takes O(n) time, and then sorting this array using Arrays.sort() which has a time complexity of O(nlogn). The space complexity is O(n) because we create an array of size n to store all the values from the input lists.

Refined Approach

Since we need the elements sorted, let us apply the k-way merge technique. The idea is pretty simple. We will construct a min heap using all the values of the lists array. Then, we will create a linked list by removing the top element of the min heap until it is empty. We are doing this because of the property of the min heap, which stores the minimum value of its values on the top. So, we will keep removing the minimum element to get a sorted linked list.

// TC: O(nlogn)
// SC: O(n)

import java.util.PriorityQueue;

class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

public class MergekSortedLists {
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for (int i = 0; i < lists.length; i++) {
            ListNode temp = lists[i];
            while (temp != null) {
                minHeap.offer(temp.val);
                temp = temp.next;
            }
        }

        if (minHeap.isEmpty()) {
            return null;
        }

        ListNode res = new ListNode(minHeap.poll());
        ListNode temp = res;
        while (!minHeap.isEmpty()) {
            temp.next = new ListNode(minHeap.poll());
            temp = temp.next;
        }

        return res;
    }

    public static void main(String args[]) {
        MergekSortedLists mksl = new MergekSortedLists();
        ListNode l1 = new ListNode(1, new ListNode(4, new ListNode(5)));
        ListNode l2 = new ListNode(1, new ListNode(3, new ListNode(4)));
        ListNode l3 = new ListNode(2, new ListNode(6));
        ListNode[] lists = { l1, l2, l3 };
        ListNode head = mksl.mergeKLists(lists);
        while (head != null) {
            System.out.print(head.val + " ");
            head = head.next;
        }
    }
}

Performance

The time complexity of the mergeKLists method is O(nlogn). This is because we are iterating through all the elements in the input lists to add them to the priority queue, which has a logn time complexity for insertion. The space complexity is O(n), as we store all the elements in the priority queue.

Efficient Approach

Let us use a divide-and-conquer approach to merge the lists. We recursively divide the array of lists into halves until it reaches base cases where there is only one or two lists to merge. The logic behind merging two sorted lists involves creating a new list that maintains the sorted order of elements from both input lists. This is achieved by comparing the current elements of both lists, selecting the smaller element to be the next in the new list, and then moving the pointer of the selected element's list forward. This process is repeated until all elements from both lists have been included in the new list. The resulting list remains sorted by always choosing the smallest available element from the two lists. This method ensures that each element is processed only once, leading to an efficient merge operation with a time complexity of O(len1+len2), where len1 and len2 are the lengths of the two lists.

// TC: O(nlogk)
// SC: O(logk)

class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

public class MergekSortedLists {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }
        return mergeKListsHelper(lists, 0, lists.length - 1);
    }

    private ListNode mergeKListsHelper(ListNode[] lists, int low, int high) {
        if (low == high) {
            return lists[low];
        }
        if (low + 1 == high) {
            return merge(lists[low], lists[high]);
        }
        int mid = low + (high - low) / 2;
        ListNode left = mergeKListsHelper(lists, low, mid);
        ListNode right = mergeKListsHelper(lists, mid + 1, high);
        return merge(left, right);
    }

    private ListNode merge(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode curr = dummy;

        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                curr.next = l1;
                l1 = l1.next;
            } else {
                curr.next = l2;
                l2 = l2.next;
            }
            curr = curr.next;
        }

        curr.next = (l1 != null) ? l1 : l2;

        return dummy.next;
    }

    public static void main(String args[]) {
        MergekSortedLists mksl = new MergekSortedLists();
        ListNode l1 = new ListNode(1, new ListNode(4, new ListNode(5)));
        ListNode l2 = new ListNode(1, new ListNode(3, new ListNode(4)));
        ListNode l3 = new ListNode(2, new ListNode(6));
        ListNode[] lists = { l1, l2, l3 };
        ListNode head = mksl.mergeKLists(lists);
        while (head != null) {
            System.out.print(head.val + " ");
            head = head.next;
        }
    }
}

Performance

The time complexity of the mergeKLists method is O(n log k). This is because there are log k levels of recursion and at each level of the recursion tree, the total work done (merging all lists at that level) is O(n) because it involves traversing all n elements once. The space complexity is O(log k) due to the recursive calls in the function.

Thank you for reading!

Check out other DSA patterns here.

You can support me by buying me a book.