Merge K sorted linked lists | Set 1

#include
using namespace std;

// class with constructor for a node of Linked list
class Node {
    public:
    int data;
    Node* next;
    // constructor
    Node(int x){
        data = x;
        next = NULL;
}
};
// This function prints data of the linked list
void print(Node* head)
{
    Node* curr = head;
    while (curr != NULL) {
        cout << curr->data << " -> ";
        curr = curr->next;
    }
    cout<<"NULL";
}

// This function merges two sorted linked lists into one sorted
// list
Node *mergeTwoLists(Node *l1, Node *l2) {
        Node dummy(INT_MIN);
        Node *tail = &dummy;
        
        while (l1 && l2) {
            if (l1->data < l2->data) {
                tail->next = l1;
                l1 = l1->next;
            } else {
                tail->next = l2;
                l2 = l2->next;
            }
            tail = tail->next;
        }

        tail->next = l1 ? l1 : l2;
        return dummy.next;
    }


// This function merges 'K' sorted lists into one sorted list
Node* mergeKLists(Node* arr[], int back)
{
    // run the while loop till 'back' is not equal to
    while (back != 0) {
        int i = 0, j = back;
 
        while (i < j) {
            // merge ith and jth list and store the list at
            // ith index of array
            arr[i] = mergeTwoLists(arr[i], arr[j]);
 
            // increment 'i' and decrement 'j' by one
            i++, j--;
 
            // update 'back' by 'j' once j is less than or
            // equal to 'i'
            if (i >= j)
                back = j;
        }
    }
 
    return arr[0];
}

// main function
int main()
{
    Node * arr[3];
    Node *head = new Node(2);
    head->next = new Node(3);
    head->next->next = new Node(5);
    Node *h2 = new Node(1);
    h2->next = new Node(4);
    h2->next->next = new Node(8);

    Node *h3 = new Node(6);
    h3->next = new Node(7);
    h3->next->next = new Node(9);

    arr[0] = head;
    arr[1] = h2;
    arr[2] = h3;
    cout<<"Final resultant merged linked list"<

						 

class Node {
	int data;
	Node next;
	Node(int data)
	{
		this.data = data;
	}
}
class MergeK 
{
	public static Node SortedMerge(Node a, Node b)
	{
		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
	public static Node mergeKLists(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];
	}
	public static void printList(Node node)
	{
		while (node != null) {
			System.out.print(node.data + " ");
			node = node.next;
		}
	}
	public static void main(String args[])
	{
		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
		Node arr[] = new Node[k];

		arr[0] = new Node(1);
		arr[0].next = new Node(3);
		arr[0].next.next = new Node(5);
		arr[0].next.next.next = new Node(7);

		arr[1] = new Node(2);
		arr[1].next = new Node(4);
		arr[1].next.next = new Node(6);
		arr[1].next.next.next = new Node(8);

		arr[2] = new Node(0);
		arr[2].next = new Node(9);
		arr[2].next.next = new Node(10);
		arr[2].next.next.next = new Node(11);

		// Merge all lists
		Node head = mergeKLists(arr, k - 1);
		printList(head);
	}
}

# A Linked List node
class Node:

    def __init__(self, x):
    
        self.data = x
        self.next = None

# Function to print nodes in
# a given linked list
def printList(node):

    while (node != None):
        print(node.data,
            end = " ")
        node = node.next

def mergeKLists(arr, last):

    for i in range(1, last + 1):
        while (True):
            head_0 = arr[0]
            head_i = arr[i]

            if (head_i == None):
                break

            if (head_0.data >=
                head_i.data):
                arr[i] = head_i.next
                head_i.next = head_0
                arr[0] = head_i
            else:
                while (head_0.next != None):
                    if (head_0.next.data >=
                        head_i.data):
                        arr[i] = head_i.next
                        head_i.next = head_0.next
                        head_0.next = head_i
                        break
                    head_0 = head_0.next
                    if (head_0.next == None):
                        arr[i] = head_i.next
                        head_i.next = None
                        head_0.next = head_i
                        head_0.next.next = None
                        break
    return arr[0]

if __name__ == '__main__':

    k = 3
    arr = [None for i in range(k)]

    arr[0] = Node(2)
    arr[0].next = Node(3)
    arr[0].next.next = Node(5)

    arr[1] = Node(1)
    arr[1].next = Node(4)
    arr[1].next.next = Node(8)

    arr[2] = Node(6)
    arr[2].next = Node(7)
    arr[2].next.next = Node(9)

    head = mergeKLists(arr, k - 1)

    print("Final resultant merged linked list")
    printList(head)