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 according to data structures in c++. 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);
    }
}

Previous post DELETE NODES FROM LINKED LIST
Next post QUICK SORT

Leave a Reply

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