Create a linked list from two linked lists by choosing max element at each position

0 0 9 minutes read

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 -> NULL

Input:
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 node
struct Node {
    int data;
    Node* next;
};
 
// Function to insert node in a linked list
void 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 list
void display(Node* root)
{
    while (root != NULL) {
        cout << root->data << " -> ";
        root = root->next;
    }
    cout << "NULL";
}
 
// Function to generate the required
// linked list and return its head
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 {
            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
int 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 approach
import java.util.*;
class GFG
{
 
// Representation of node
static class Node 
{
    int data;
    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) 
    {
        System.out.print( root.data + " - > ");
        root = root.next;
    }
    System.out.print("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 is contributed by Arnab Kundu

Python3

# Python3 implementation of the approach
import math
 
# Representation of node
class Node: 
    def __init__(self, data): 
        self.data = data 
        self.next = None
 
# Function to insert node in a linked list
def 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 list
def display(root):
    while (root != None) :
        print(root.data, end = "->")
        root = root.next
     
    print("NULL")
 
# Function to generate the required
# linked list and return its head
def 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 code
if __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 approach
using 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 node
class 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 zambiatek!