DSA Decoded | Day 25: Merge K Sorted Linked Lists

Photo by Susan Kirsch on Unsplash

“This is a running series of posts, where I solve DSA problems and try to explain them as thoroughly as possible for anyone to understand. Usually I’ll be using JAVA for solving all problems”

The link to this question is provided below

Merge K Sorted Linked Lists - NeetCode

Problem Statement:

You are given an array of k linked lists lists, where each list is sorted in ascending order.

Return the sorted linked list that is the result of merging all of the individual linked lists.

Example 1:

Input: lists = [[1,2,4],[1,3,5],[3,6]]

Output: [1,1,2,3,3,4,5,6]

Constraints:

• 0 <= lists.length <= 1000
• 0 <= lists[i].length <= 100
• -1000 <= lists[i][j] <= 1000

Intuition:

Get Mayank Kumar Shaw’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

A simple workflow is :

1. Keep an auxillary listnode that is going to be used as resulting list.
2. Merge every list with this auxillary list.
3. Merge when node in list2 is ≤ the current node in auxillary node. Else move forward.

Solution:

/**
 * 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) {
        ListNode res = null;

        for(ListNode head : lists){
            res = merge(res, head);
        }

        return res;
    }

    public ListNode merge(ListNode a, ListNode b){
        if(a == null) return b;
        if(b == null) return a;

        ListNode prev = null, temp = null;
        ListNode t1 = a, t2 = b;
        
        while(t2 != null && t1 != null){
            if(t2.val <= t1.val){ // insert bw prev and t1
                temp = t2.next;

                if(prev == null){
                    prev = t2;
                    t2.next = t1;
                    a = prev;   // head of main list
                }else{
                    prev.next = t2;
                    t2.next = t1;
                    prev = t2;
                }

                t2 = temp;
            }else{
                prev = t1;
                t1 = t1.next;
            }
        }

        if(t2 != null){
            prev.next = t2;
        }

        return a;
    }
}

Complexity:

Time : O(n^2) , we do linear merging for all lists.

Space : O(1) , we use two pointers.