Given two linked list of equal sizes, the task is to create new linked list using those linked lists where at every step, the maximum of the two elements from both the linked lists is chosen and the other is skipped.
Examples:
Input:
list1 = 5 -> 2 -> 3 -> 8 -> NULL
list2 = 1 -> 7 -> 4 -> 5 -> NULL
Output: 5 -> 7 -> 4 -> 8 -> NULLInput:
list1 = 2 -> 8 -> 9 -> 3 -> NULL
list2 = 5 -> 3 -> 6 -> 4 -> NULL
Output: 5 -> 8 -> 9 -> 4 -> NULL
A linked list is a data structure where each element is connected to the next element in the list. In this task, we have two linked lists and we want to create a new linked list by picking the maximum element from each position of the two original linked lists and placing it in the same position in the new linked list.
For example, let’s say we have two linked lists:
List 1: [1, 3, 5, 7]
List 2: [2, 4, 6, 8]
To create the new linked list, we compare the first elements of both original linked lists, which are 1 and 2. We pick the maximum of these two, which is 2, and place it in the first position of the new linked list.
Next, we compare the second elements of both original linked lists, which are 3 and 4. We pick the maximum of these two, which is 4, and place it in the second position of the new linked list.
We repeat this process for all elements in both linked lists, until we have gone through all elements in both linked lists.
So, the new linked list would be: [2, 4, 6, 8]
This is how we can create a new linked list by choosing the maximum element at each position from two linked lists.
Approach: We traverse both the linked list at the same time and compare node from both the lists. The node which is greater among them, will be added to the new linked list. We do this for each node and then print the nodes of the generated linked list.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <iostream>using namespace std;// Representation of nodestruct Node { int data; Node* next;};// Function to insert node in a linked listvoid insert(Node** root, int item){ Node *ptr, *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; }}// Function to print the// nodes of a linked listvoid display(Node* root){ while (root != NULL) { cout << root->data << " -> "; root = root->next; } cout << "NULL";}// Function to generate the required// linked list and return its headNode* newList(Node* root1, Node* root2){ Node *ptr1 = root1, *ptr2 = root2; Node* root = NULL; // While there are nodes left while (ptr1 != NULL) { // Maximum node at current position int currMax = ((ptr1->data < ptr2->data) ? ptr2->data : ptr1->data); // If current node is the first node // of the newly linked list being // generated then assign it to the root if (root == NULL) { Node* temp = new Node; temp->data = currMax; temp->next = NULL; root = temp; } // Else insert the newly // created node in the end else { insert(&root, currMax); } // Get to the next nodes ptr1 = ptr1->next; ptr2 = ptr2->next; } // Return the head of the // generated linked list return root;}// Driver codeint main(){ Node *root1 = NULL, *root2 = NULL, *root = NULL; // First linked list insert(&root1, 5); insert(&root1, 2); insert(&root1, 3); insert(&root1, 8); // Second linked list insert(&root2, 1); insert(&root2, 7); insert(&root2, 4); insert(&root2, 5); // Generate the new linked list // and get its head root = newList(root1, root2); // Display the nodes of the generated list display(root); return 0;} |
Java
// Java implementation of the approachimport java.util.*;class GFG{// Representation of nodestatic class Node { int data; Node next;};// Function to insert node in a linked liststatic Node insert(Node root, int item){ Node ptr, 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; } return root;}// Function to print the// nodes of a linked liststatic void display(Node root){ while (root != null) { System.out.print( root.data + " - > "); root = root.next; } System.out.print("null");}// Function to generate the required// linked list and return its headstatic Node newList(Node root1, Node root2){ Node ptr1 = root1, ptr2 = root2; Node root = null; // While there are nodes left while (ptr1 != null) { // Maximum node at current position int currMax = ((ptr1.data < ptr2.data) ? ptr2.data : ptr1.data); // If current node is the first node // of the newly linked list being // generated then assign it to the root if (root == null) { Node temp = new Node(); temp.data = currMax; temp.next = null; root = temp; } // Else insert the newly // created node in the end else { root = insert(root, currMax); } // Get to the next nodes ptr1 = ptr1.next; ptr2 = ptr2.next; } // Return the head of the // generated linked list return root;}// Driver codepublic static void main(String args[]){ Node root1 = null, root2 = null, root = null; // First linked list root1 = insert(root1, 5); root1 = insert(root1, 2); root1 = insert(root1, 3); root1 = insert(root1, 8); // Second linked list root2 = insert(root2, 1); root2 = insert(root2, 7); root2 = insert(root2, 4); root2 = insert(root2, 5); // Generate the new linked list // and get its head root = newList(root1, root2); // Display the nodes of the generated list display(root);}}// This code is contributed by Arnab Kundu |
Python3
# Python3 implementation of the approachimport math# Representation of nodeclass Node: def __init__(self, data): self.data = data self.next = None# Function to insert node in a linked listdef insert(root, item): #ptr, *temp temp = Node(item) temp.data = item temp.next = None if (root == None): root = temp else: ptr = root while (ptr.next != None): ptr = ptr.next ptr.next = temp return root# Function to print the# nodes of a linked listdef display(root): while (root != None) : print(root.data, end = "->") root = root.next print("NULL")# Function to generate the required# linked list and return its headdef newList(root1, root2): ptr1 = root1 ptr2 = root2 root = None # While there are nodes left while (ptr1 != None) : # Maximum node at current position currMax = ((ptr1.data < ptr2.data) and ptr2.data or ptr1.data) # If current node is the first node # of the newly linked list being # generated then assign it to the root if (root == None): temp = Node(currMax) temp.data = currMax temp.next = None root = temp # Else insert the newly # created node in the end else : root = insert(root, currMax) # Get to the next nodes ptr1 = ptr1.next ptr2 = ptr2.next # Return the head of the # generated linked list return root# Driver codeif __name__=='__main__': root1 = None root2 = None root = None # First linked list root1 = insert(root1, 5) root1 = insert(root1, 2) root1 = insert(root1, 3) root1 = insert(root1, 8) # Second linked list root2 = insert(root2, 1) root2 = insert(root2, 7) root2 = insert(root2, 4) root2 = insert(root2, 5) # Generate the new linked list # and get its head root = newList(root1, root2) # Display the nodes of the generated list display(root)# This code is contributed by Srathore |
C#
// C# implementation of the approachusing System; class GFG { // Representation of node public class Node { public int data; public Node next; }; // Function to insert node in a linked list static Node insert(Node root, int item) { Node ptr, 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; } return root; } // Function to print the // nodes of a linked list static void display(Node root) { while (root != null) { Console.Write( root.data + " - > "); root = root.next; } Console.Write("null"); } // Function to generate the required // linked list and return its head static Node newList(Node root1, Node root2) { Node ptr1 = root1, ptr2 = root2; Node root = null; // While there are nodes left while (ptr1 != null) { // Maximum node at current position int currMax = ((ptr1.data < ptr2.data) ? ptr2.data : ptr1.data); // If current node is the first node // of the newly linked list being // generated then assign it to the root if (root == null) { Node temp = new Node(); temp.data = currMax; temp.next = null; root = temp; } // Else insert the newly // created node in the end else { root = insert(root, currMax); } // Get to the next nodes ptr1 = ptr1.next; ptr2 = ptr2.next; } // Return the head of the // generated linked list return root; } // Driver code public static void Main(String []args) { Node root1 = null, root2 = null, root = null; // First linked list root1 = insert(root1, 5); root1 = insert(root1, 2); root1 = insert(root1, 3); root1 = insert(root1, 8); // Second linked list root2 = insert(root2, 1); root2 = insert(root2, 7); root2 = insert(root2, 4); root2 = insert(root2, 5); // Generate the new linked list // and get its head root = newList(root1, root2); // Display the nodes of the generated list display(root); } } /* This code contributed by PrinciRaj1992 */ |
Javascript
<script>// javascript implementation of the approach // Representation of nodeclass Node { constructor() { this.data = 0; this.next = null; }} // Function to insert node in a linked list function insert( root , item) { var ptr, 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; } return root; } // Function to print the // nodes of a linked list function display( root) { while (root != null) { document.write(root.data + " - > "); root = root.next; } document.write("null"); } // Function to generate the required // linked list and return its head function newList( root1, root2) { ptr1 = root1, ptr2 = root2; root = null; // While there are nodes left while (ptr1 != null) { // Maximum node at current position var currMax = ((ptr1.data < ptr2.data) ? ptr2.data : ptr1.data); // If current node is the first node // of the newly linked list being // generated then assign it to the root if (root == null) { temp = new Node(); temp.data = currMax; temp.next = null; root = temp; } // Else insert the newly // created node in the end else { root = insert(root, currMax); } // Get to the next nodes ptr1 = ptr1.next; ptr2 = ptr2.next; } // Return the head of the // generated linked list return root; } // Driver code root1 = null, root2 = null, root = null; // First linked list root1 = insert(root1, 5); root1 = insert(root1, 2); root1 = insert(root1, 3); root1 = insert(root1, 8); // Second linked list root2 = insert(root2, 1); root2 = insert(root2, 7); root2 = insert(root2, 4); root2 = insert(root2, 5); // Generate the new linked list // and get its head root = newList(root1, root2); // Display the nodes of the generated list display(root);// This code is contributed by todaysgaurav.</script> |
Output:
5 -> 7 -> 4 -> 8 -> NULL
Time complexity: O(n) where n is size of linked list
Space complexity: O(n) where n is size of newly created linked list
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
