MERGE K SORTED LINKED LISTS

Concepts Used

Linked lists, Heaps/priority queue(efficient soltution)

Difficulty Level

Hard

Problem Statement :

Yor are given K sorted linked lists. You have to merge K sorted linked lists into one sorted list. The size of the linked list maybe different.

See original problem statement here

Example:

Input:
[
list[1]:4βˆ’>6βˆ’>8βˆ’>10βˆ’>15
list[2]:1βˆ’>5βˆ’>9
list[3]:2βˆ’>3βˆ’>7βˆ’>11
]

Output: 
1βˆ’>2βˆ’>3βˆ’>4βˆ’>5βˆ’>6βˆ’>7βˆ’>8βˆ’>9βˆ’>10βˆ’>11βˆ’>15

EXPLANATION:

Approach 1(Brute force):

All the given lists are sorted, which means that the head of each list would be the smallest element in its chain. So we could extract the minimum from the k head nodes and append it to the result list.

Time complexity: O(kN) where k is the number of linked lists.Almost every selection of nodes in final linked costs O(k) (k-1 times comparison).

Space complexity: O(1).

Approach 2:

The idea is to insert all the node values from all the k lists into an array. Sorting the array and creating a new linked list from the sorted array will give the required output.

Pseudo code:

     ListNode mergeKLists(ListNode[] lists, int k)
     {
    // x array to store all the values from lists
    int x[]
    for(i = 0 to k) 
    {
        ListNode temp = lists[i]
        while(temp is not null)
       {
            // append the value of temp to x
            x.add(temp.val)
            temp = temp.next
        }
    }
    // sort all the values of x
    sort(x)
    // Head node to return
    ListNode head(-1)
    ListNode temp = head
    for(i = 0 to x.size()) {
        ListNode newVal(x[i])
        temp.next = newVal
        temp = temp.next
    }
    return head.next
    } 

>TIME COMPLEXITY: O(NlogN).
>SPACE COMPLEXITY: O(N),
>where N is the total number of nodes

Approach 3(Heaps):

Create a priority queue.Insert the first node from all the lists into the priority queue.Loop until the priority queue is not empty Extract the minimum node from the queue and add it to our result list.Add the next node (if present) from the extracted node list.
Return the resultant list.

SOLUTIONS:

#include <bits/stdc++.h> 
using namespace std; 

struct Node { 
    int data; 
    struct Node* next; 
}; 
struct compare { 
    bool operator()(struct Node* a, struct Node* b) 
    { 
        return a->data > b->data; 
    } 
}; 

struct Node* mergeKSortedLists(struct Node* arr[], int k) 
{ 
    struct Node *head = NULL, *last; 
    priority_queue<Node*, vector<Node*>, compare> pq; 
    for (int i = 0; i < k; i++) 
        if (arr[i] != NULL) 
            pq.push(arr[i]); 

    while (!pq.empty()) { 
        struct Node* top = pq.top(); 
        pq.pop(); 
        if (top->next != NULL)  
            pq.push(top->next); 
        if (head == NULL) { 
            head = top; 
            last = top; 
        } 

        else {  
            last->next = top; 
            last = top; 
        } 
    } 
    return head; 
} 
void printList(struct Node* head) 
{ 
    while (head != NULL) { 
        cout << head->data << " "; 
        head = head->next; 
    } 
} 
struct Node* newNode(int data) 
{ 
    struct Node* new_node = new Node(); 
    new_node->data = data; 
    new_node->next = NULL; 

    return new_node; 
}  
int main() 
{ 
    int k;cin>>k;
    Node* arr[k]; 
    for(int i=0;i<k;i++)
    {
      int n;cin>>n;
      int x;cin>>x;
      arr[i]=newNode(x);
      Node* head=arr[i];
      for(int j=1;j<n;j++)
      {
        cin>>x;
        head->next=newNode(x);
        head=head->next;
      }
    }
    struct Node* head = mergeKSortedLists(arr, k);
    printList(head); 

    return 0; 
    }
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.*;
class Node {
    int data;
    Node next;

    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}

public class Main
{
    public static void printList(Node node) {
        while (node != null) {
            System.out.print(node.data + " ");
            node = node.next;
        }
    }
    public static Node mergeKLists(Node[] list, int k)
    {
        PriorityQueue<Node> pq;
        pq = new PriorityQueue(Comparator.comparingInt(a -> ((Node) a).data));
        pq.addAll(Arrays.asList(list).subList(0, k));
        Node head = null, last = null;
        while (!pq.isEmpty())
        {
            Node min = pq.poll();
            if (head == null) {
                head = last = min;
            } else {
                last.next = min;
                last = min;
            }
            if (min.next != null) {
                pq.add(min.next);
            }
        }
        return head;
    }

    public static void main(String[] s) {
        Scanner sc = new Scanner(System.in);
        int k= sc.nextInt();
        Node[] list = new Node[k];
        for(int i=0;i<k;i++){
            int n = sc.nextInt();
          int x=sc.nextInt();

        list[i] = new Node(x);
        Node head=list[i];
        for(int j=1;j<n;j++)
        {
          x=sc.nextInt();
          head.next=new Node(x);
          head=head.next;
        }
        }
        Node headnew = mergeKLists(list, k);
        printList(headnew);
    }
}

[forminator_quiz id="1808"]

This article tried to discuss Linked lists, Heaps/priority queue. Hope this blog helps you understand and solve the problem. To practice more problems on Linked lists, Heaps, Priority queue you can check out MYCODE | Competitive Programming.

Leave a Reply

Your email address will not be published. Required fields are marked *