Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email
Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!
Linked list articles

MERGE K SORTED LINKED LISTS

Shaily

Last Updated on November 28, 2022 by Prepbytes

In this blog, we will discuss three different approaches to merge k sorted lists. Merging k sorted linked lists is a challenging topic and conquering it will make your data structures more efficient. Let’s discuss how to merge k sorted lists.

How to Merge K Sorted Linked List?

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 To Merge K Sorted Lists(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 To Merge K Sorted Lists In Brute Force approach: O(kN) where k is the number of linked lists. Almost every selection of nodes in the final link costs O(k) (k-1 times comparison).

Space complexity To Merge K Sorted Lists: O(1).

Approach 2 To Merge K Sorted Lists:

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 To Merge K Sorted Lists: O(NlogN).
SPACE COMPLEXITY To Merge K Sorted Lists: O(N),
where N is the total number of nodes

Approach 3 To Merge K Sorted Lists(Heaps):

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

SOLUTIONS To Merge K Sorted Lists:

#include
#include

struct Node {
    int data;
    struct Node* next;
};
 
/* Function to print nodes in
   a given linked list */
void printList(struct Node* node)
{
    while (node != NULL) {
        printf("%d ", node->data);
        node = node->next;
    }
}
 
/* Takes two lists sorted in increasing order, and merge
   their nodes together to make one big sorted list. Below
   function takes O(n) extra space for recursive calls,
    */
struct Node* SortedMerge(struct Node* a,struct Node* b)
{
    struct Node* result = NULL;
 
    /* Base cases */
    if (a == NULL)
        return (b);
    else if (b == NULL)
        return (a);
 
    /* Pick either a or b, and recur */
    if (a->data <= b->data) {
        result = a;
        result->next = SortedMerge(a->next, b);
    }
    else {
        result = b;
        result->next = SortedMerge(a, b->next);
    }
 
    return result;
}
 
// The main function that takes an array of lists
// arr[0..last] and generates the sorted output
struct Node* mergeKLists(struct Node* arr[], int last)
{
    // repeat until only one list is left
    while (last != 0) {
        int i = 0, j = last;
 
        // (i, j) forms a pair
        while (i < j) {
            // merge List i with List j and store
            // merged list in List i
            arr[i] = SortedMerge(arr[i], arr[j]);
 
            // consider next pair
            i++, j--;
 
            // If all pairs are merged, update last
            if (i >= j)
                last = j;
        }
    }
 
    return arr[0];
}
 
// Utility function to create a new node.
struct Node* newNode(int data)
{
    struct Node* temp =
           (struct Node*) malloc(sizeof(struct Node));
    temp->data = data;
    temp->next = NULL;
    return temp;
}
 
// Driver program to test above functions
int main()
{
    int k = 3; // Number of linked lists
    int n = 4; // Number of elements in each list
 
    // an array of pointers storing the head nodes
    // of the linked lists
    struct Node* arr[k];
 
    arr[0] = newNode(1);
    arr[0]->next = newNode(3);
    arr[0]->next->next = newNode(5);
    arr[0]->next->next->next = newNode(7);
 
    arr[1] = newNode(2);
    arr[1]->next = newNode(4);
    arr[1]->next->next = newNode(6);
    arr[1]->next->next->next = newNode(8);
 
    arr[2] = newNode(0);
    arr[2]->next = newNode(9);
    arr[2]->next->next = newNode(10);
    arr[2]->next->next->next = newNode(11);
 
    // Merge all lists
    struct Node* head = mergeKLists(arr, k - 1);
 
    printList(head);
 
    return 0;
}

#include  
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, 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>n;
      int x;cin>>x;
      arr[i]=newNode(x);
      Node* head=arr[i];
      for(int j=1;j>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 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


						 
import heapq
from heapq import heappop, heappush
class Node:
    def __init__(self, data, next=None):
        self.data = data
        self.next = next
 
    def __lt__(self, other):
        return self.data < other.data
 
 
def printList(node):
    while node:
        print(node.data, end=' —> ')
        node = node.next
 
    print('None')
 
 
def mergeKLists(lists):
 
    pq = [x for x in lists]
    heapq.heapify(pq)
 
    head = last = None
 
    while pq:
 
        min = heappop(pq)
 
        if head is None:
            head = min
            last = min
        else:
            last.next = min
            last = min
 
        if min.next:
            heappush(pq, min.next)
 
    return head
 
 
if __name__ == '__main__':
 
    k = 3
 
    lists = [None] * k
 
    lists[0] = Node(4)
    lists[0].next = Node(6)
    lists[0].next.next = Node(8)
    lists[0].next.next.next = Node(10)
    lists[0].next.next.next.next = Node(15)
 
    lists[1] = Node(1)
    lists[1].next = Node(5)
    lists[1].next.next = Node(9)
 
    lists[2] = Node(2)
    lists[2].next = Node(3)
    lists[2].next.next = Node(7)
    lists[2].next.next.next = Node(11)
 
    head = mergeKLists(lists)
    printList(head)

This blog discusses different approaches for figuring out how to merge k sorted lists. Every approach is important as knowing that will help you to understand the advantages and disadvantages of that approach. Targeting topics of data structures like Linked lists, Heaps, Priority queue will definitely help you to grab your dream job. For Practicing more questions, you can check out MYCODE | Competitive Programming.

FAQ

1. How do I merge two sorted lists?
Merge two sorted linked lists using Dummy Nodes:

  • First, make a dummy node for the new merged linked list.
  • Now make two pointers, one will point to list1 and another will point to list2.
  • Now traverse the lists till one of them gets exhausted.

2. Which companies have recently asked how to merge k sorted lists?
Samsung, SquadStack, Amazon, and Josh Technologies in their recent technical interviews have asked this question.

Leave a Reply

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

Close

Related Post