Merge k sorted singly linked list

Given k sorted singly-linked lists, write a function to merge all the lists into one sorted singly linked list.

Example:

Input:  list1: 1->3->4->NULL, list2: 3->5->6->NULL, list3: 2->4->5->7->NULL
Output: New list
1 2 3 3 4 4 5 5 6 7 

Approach

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;
}