Linked List: Given 2 linked list by choosing max element at each position

Problem Statement:

You are given 2 LL of equal size.

You need to create new linked list by taking max of the 2 elements from both the linked list.

Example:

Input: 
list1 = 6 -> 2 -> 1 -> 10 -> NULL 
list2 = 2 -> 8 -> 5 -> 7 -> NULL 

Output:

6 -> 8 -> 5 -> 10 -> NULL

Solution Explanation:

Traverse both linked list at the same time.

Compare the nodes from both of the LL.

Take the node that is greater between the two nodes.

Add the value into the new LL.

Do this for all the nodes

Time Complexity: O(n)
Space Complexity: O(n)

Code Solution

#include <iostream>
using namespace std;

struct Node 
{
	int data;
	Node* next;
};

void insert(Node** root, int item)
{
	Node *ptr;
	Node *temp;

	temp = new Node;
	temp->data = item;
	temp->next = NULL;

	if (*root == NULL)
		*root = temp;

	else 
	{
		ptr = *root;
		while (ptr->next != NULL)
			ptr = ptr->next;

		ptr->next = temp;
	}
}


void display(Node* root)
{
	while (root != NULL) 
	{
		cout << root->data << " -> ";
		root = root->next;
	}
	cout << "NULL";
}


Node* solution(Node* root1, Node* root2)
{
	Node *ptr1 = root1;
	Node *ptr2 = root2;
	Node* root = NULL;

	while (ptr1 != NULL) 
	{

		int currMax = ((ptr1->data < ptr2->data)
						? ptr2->data
						: ptr1->data);


		if (root == NULL) 
		{
			Node* temp = new Node;
			temp->data = currMax;
			temp->next = NULL;
			root = temp;
		}

		else 
		{
			insert(&root, currMax);
		}

 		ptr1 = ptr1->next;
		ptr2 = ptr2->next;
	}

	return root;
}

int main()
{
	Node *root1 = NULL;
	Node *root2 = NULL;
	Node *root = NULL;

	// first list
	insert(&root1, 6);
	insert(&root1, 2);
	insert(&root1, 1);
	insert(&root1, 10);

	// second list
	insert(&root2, 2);
	insert(&root2, 8);
	insert(&root2, 5);
	insert(&root2, 7);


	// and get its head
	root = solution(root1, root2);

	display(root);

	return 0;
}

Output

6 -> 8 -> 5 -> 10 -> NULL