Merge k Sorted Lists

Merge K sorted the linked list into one linked list.

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

Merge all the linked-lists into one sorted linked-list and return it.

Example:

Input: l1= 1->3->4->NULL, l2=3->5->6, l3=2->4->5->7
Output: 1->2->3->3->4->4->5->5->6->7->NULL

Approach: 1

Java

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;

public class MergeKSortedList {
    public static void main(String[] args) {
        // Linked list list to hold all linked list
        List<ListNode> lists = new ArrayList<ListNode>();

        // create first list
        ListNode l1 = new ListNode(1);
        l1.next = new ListNode(2);
        l1.next.next = new ListNode(3);
        l1.next.next.next = new ListNode(4);
        l1.next.next.next.next = new ListNode(5);
        lists.add(l1);
        // second list
        ListNode l2 = new ListNode(1);
        l2.next = new ListNode(2);
        l2.next.next = new ListNode(3);
        l2.next.next.next = new ListNode(4);
        l2.next.next.next.next = new ListNode(5);
        lists.add(l2);
        // third list
        ListNode l3 = new ListNode(1);
        l3.next = new ListNode(5);
        l3.next.next = new ListNode(8);
        lists.add(l3);
        // call for mergeKLists

        ListNode merge = mergeKLists(lists);
        System.out.println("Merge List is");
        linkedListTraversal(merge);
    }

    // method for merge K list
    private static ListNode mergeKLists(List<ListNode> lists) {
        if (lists.size() == 0)
            return null;
        ListNode merge = lists.get(0);
        // iterate till end of list
        for (int i = 1; i < lists.size(); i++) {
            // merge two lists
            ListNode next = lists.get(i);
            merge = merge(merge, next);
        }
        return merge;
    }

    // method for merge two list
    private static ListNode merge(ListNode merge, ListNode next) {
        // base condition
        if (merge == null)
            return next;
        if (next == null)
            return merge;
        ListNode tmp1 = merge;
        ListNode tmp2 = next;
        ListNode root = null;
        ListNode tmp = null;
        int flag = 0;
        while (tmp1 != null && tmp2 != null) {
            // first less then
            if (tmp1.val < tmp2.val) {
                if (flag == 0) {
                    flag = 1;
                    root = tmp1;
                    tmp = root;
                } else {
                    tmp.next = tmp1;
                    tmp = tmp.next;
                }
                tmp1 = tmp1.next;
            } else {
                if (flag == 0) {
                    flag = 1;
                    root = tmp2;
                    tmp = root;
                } else {
                    tmp.next = tmp2;
                    tmp = tmp.next;

                }
                if (tmp2 != null)
                    tmp2 = tmp2.next;
            }
        }
        if (tmp1 != null)
            tmp.next = tmp1;
        if (tmp2 != null)
            tmp.next = tmp2;
        return root;

    }

    // method for traversal list
    private static void linkedListTraversal(ListNode node) {
        while (node != null) {
            System.out.print(node.val + " ");
            node = node.next;
        }
    }
}


class ListNode implements Comparable<ListNode> {
    int val;
    ListNode next;

    ListNode() {
    }

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

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

    @Override
    public int compareTo(ListNode o) {
        if (this.val == o.val)
            return 0;
        else if (this.val > o.val)
            return 1;
        else
            return -1;
    }
}

C++

#include <bits/stdc++.h>
using namespace std;
//Struture of  node
struct Node
{ 
   int data;
   Node *next;
   Node(int data)
    {
        this->data=data;
        this->next=NULL;
    }
};

//function to traverse a linked 
//list
void linkedListTraversal(Node *head)
{
    Node *temp=head;
    //iterate till we reach end of the linked 
    //list
    while(temp!=NULL)
     {
         //print the current
         //node data
         cout<<temp->data<<" ";
         //move to next node
         temp=temp->next;
     }
}

//function to merge two sorted lists
Node *merge(Node *l1,Node *l2)
    {
        if(l1==NULL)
              return l2;
        if(l2==NULL)
              return l1;
        Node *temp1=l1,*temp2=l2,*root=NULL,*temp;
        int flag=0;
        while(temp1!=NULL &&temp2!=NULL)
        {
            if(temp1->data<temp2->data)
            {
                if(flag==0)
                {
                    flag=1;
                    root=temp1;
                    temp=root;
                }
              else
              {
                  temp->next=temp1;
                  
                  temp=temp->next;
              }
                temp1=temp1->next;
            }
            else
            {
                if(flag==0)
                {
                    flag=1;
                    root=temp2;
                    temp=root;
                }
                else
                {
                    temp->next=temp2;
                  
                    temp=temp->next;
                }
                  temp2=temp2->next;
            }
        }
        if(temp1!=NULL)
               temp->next=temp1;
        if(temp2!=NULL)
               temp->next=temp2;
        return root;
}

//function to merge k sorted list
Node* mergeKLists(vector<Node*>& lists) 
{
    if(lists.size()==0)
               return NULL;
    Node *l=lists[0];
     for(int i=1;i<lists.size();i++)
       {
        //merge two lists
        Node *temp1=lists[i];
       l =merge(l,temp1);
       }
     return l;
}
int main()
{

  //list 1: 1->3->4
  Node *l1=new Node(1);
  l1->next=new Node(3);
  l1->next->next=new Node(4);

  //list 2: 3->5->6
  Node *l2=new Node(3);
  l2->next=new Node(5);
  l2->next->next=new Node(6);

  //list 3: 2->4->5->7
  Node *l3=new Node(2);
  l3->next=new Node(4);
  l3->next->next=new Node(5);
  l3->next->next->next=new Node(7);

  //vector to hold the all lists
  vector<Node*> lists;
  lists.push_back(l1);
  lists.push_back(l2);
  lists.push_back(l3);

  //call for mergeKLists
  Node *node= mergeKLists(lists);
  cout<<"New list\n";
  linkedListTraversal(node);
  return 0;
}

Approach 2: Effective Approach

Java

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;

public class MergeKSortedList1 {
    public static void main(String[] args) {
        // Linked list list to hold all linked list
        List<ListNode> lists = new ArrayList<ListNode>();

        // create first list
        ListNode l1 = new ListNode(1);
        l1.next = new ListNode(2);
        l1.next.next = new ListNode(3);
        l1.next.next.next = new ListNode(4);
        l1.next.next.next.next = new ListNode(5);
        lists.add(l1);
        // second list
        ListNode l2 = new ListNode(1);
        l2.next = new ListNode(2);
        l2.next.next = new ListNode(3);
        l2.next.next.next = new ListNode(4);
        l2.next.next.next.next = new ListNode(5);
        lists.add(l2);
        // third list
        ListNode l3 = new ListNode(1);
        l3.next = new ListNode(5);
        l3.next.next = new ListNode(8);
        lists.add(l3);
        // call for mergeKLists

        ListNode merge = mergeKListsK(lists);
        System.out.println("Merge List is");
        linkedListTraversal(merge);
    }

    // method for merge k list
    public static ListNode mergeKListsK(List<ListNode> lists) {
        // base condition
        if (lists == null || lists.size() == 0)
            return null;
        // Declare priority queue for this ListNode must 
        //be comparable
        PriorityQueue<ListNode> pq = new PriorityQueue<>
      (lists.size());
        // iterate till end of list
        for (ListNode node : lists) {
            // add into queus
            if (node != null)
                pq.add(node);
        }
        // create new list
        ListNode list = new ListNode(0);
        ListNode result = list;
        // iterate till queue empty
        while (!pq.isEmpty()) {
            // poll from queue
            ListNode node1 = pq.poll();
            list.next = node1;
            list = list.next;
            // add next node into queue
            if (node1.next != null)
                pq.add(node1.next);
        }
        return result.next;
    }

    // method for traversal list
    private static void linkedListTraversal(ListNode node) {
        while (node != null) {
            System.out.print(node.val + " ");
            node = node.next;
        }
    }
}


class ListNode implements Comparable<ListNode> {
    int val;
    ListNode next;

    ListNode() {
    }

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

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

    @Override
    public int compareTo(ListNode o) {
        if (this.val == o.val)
            return 0;
        else if (this.val > o.val)
            return 1;
        else
            return -1;
    }
}