Create new linked list from two given linked list with greater element at each node

Last Updated : 11 Jul, 2022

Given two linked list of the same size, the task is to create a new linked list using those linked lists. The condition is that the greater node among both linked list will be added to the new linked list.
Examples:

Input:  list1 = 5->2->3->8
list2 = 1->7->4->5
Output:  New list = 5->7->4->8

Input: list1 = 2->8->9->3
list2 = 5->3->6->4
Output:  New list = 5->8->9->4

Approach: We traverse both the linked list at the same time and compare node of both lists. The node which is greater among them will be added to the new linked list. We do this for each node.

C++

// C++ program to create a new linked list
// from two given linked list
// of the same size with
// the greater element among the two at each node
 
#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 which returns new linked list
Node* newList(Node* root1, Node* root2)
{
    Node *ptr1 = root1, *ptr2 = root2, *ptr;
    Node *root = NULL, *temp;
 
    while (ptr1 != NULL) {
        temp = new Node;
        temp->next = NULL;
 
        // Compare for greater node
        if (ptr1->data < ptr2->data)
            temp->data = ptr2->data;
        else
            temp->data = ptr1->data;
 
        if (root == NULL)
            root = temp;
        else {
            ptr = root;
            while (ptr->next != NULL)
                ptr = ptr->next;
 
            ptr->next = temp;
        }
        ptr1 = ptr1->next;
        ptr2 = ptr2->next;
    }
    return root;
}
 
void display(Node* root)
{
    while (root != NULL) {
        cout << root->data << "->";
        root = root->next;
    }
 
    cout << endl;
}
 
// 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);
 
    cout << "First List:  ";
    display(root1);
 
    // Second linked list
    insert(&root2, 1);
    insert(&root2, 7);
    insert(&root2, 4);
    insert(&root2, 5);
 
    cout << "Second List: ";
    display(root2);
 
    root = newList(root1, root2);
    cout << "New List:    ";
    display(root);
    return 0;
}

Java

// Java program to create a new linked list 
// from two given linked list 
// of the same size with 
// the greater element among the two at each node 
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 which returns new linked list 
static Node newList(Node root1, Node root2) 
{ 
    Node ptr1 = root1, ptr2 = root2, ptr; 
    Node root = null, temp; 
 
    while (ptr1 != null) { 
        temp = new Node(); 
        temp.next = null; 
 
        // Compare for greater node 
        if (ptr1.data < ptr2.data) 
            temp.data = ptr2.data; 
        else
            temp.data = ptr1.data; 
 
        if (root == null) 
            root = temp; 
        else { 
            ptr = root; 
            while (ptr.next != null) 
                ptr = ptr.next; 
 
            ptr.next = temp; 
        } 
        ptr1 = ptr1.next; 
        ptr2 = ptr2.next; 
    } 
    return root; 
} 
 
static void display(Node root) 
{ 
    while (root != null) 
    { 
        System.out.print( root.data + "->"); 
        root = root.next; 
    } 
    System.out.println();
} 
 
// 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); 
 
    System.out.print("First List: "); 
    display(root1); 
 
    // Second linked list 
    root2=insert(root2, 1); 
    root2=insert(root2, 7); 
    root2=insert(root2, 4); 
    root2=insert(root2, 5); 
 
    System.out.print( "Second List: "); 
    display(root2); 
 
    root = newList(root1, root2); 
    System.out.print("New List: "); 
    display(root); 
} 
}
 
// This code is contributed by Arnab Kundu

Python3

# Python3 program to create a 
# new linked list from two given 
# linked list of the same size with
# the greater element among the two
# at each node
 
# Node class 
class Node: 
 
    # Function to initialise the node object 
    def __init__(self, data): 
        self.data = data 
        self.next = None
 
# Function to insert node in a linked list
def insert(root, item):
 
    temp = Node(0)
    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 which returns new linked list
def newList(root1, root2):
 
    ptr1 = root1
    ptr2 = root2
     
    root = None
    while (ptr1 != None) :
        temp = Node(0)
        temp.next = None
 
        # Compare for greater node
        if (ptr1.data < ptr2.data):
            temp.data = ptr2.data
        else:
            temp.data = ptr1.data
 
        if (root == None):
            root = temp
        else :
            ptr = root
            while (ptr.next != None):
                ptr = ptr.next
 
            ptr.next = temp
         
        ptr1 = ptr1.next
        ptr2 = ptr2.next
     
    return root
 
def display(root):
 
    while (root != None) :
        print(root.data, "->", end = " ")
        root = root.next
     
    print(" ");
 
# 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)
 
    print("First List: ", end = " ")
    display(root1)
 
    # Second linked list
    root2 = insert(root2, 1)
    root2 = insert(root2, 7)
    root2 = insert(root2, 4)
    root2 = insert(root2, 5)
 
    print("Second List: ", end = " ")
    display(root2)
 
    root = newList(root1, root2)
    print("New List: ", end = " ")
    display(root)
 
# This code is contributed by Arnab Kundu

C#

// C# program to create a new linked list 
// from two given linked list 
// of the same size with 
// the greater element among the two at each node 
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 which returns new linked list 
static Node newList(Node root1, Node root2) 
{ 
    Node ptr1 = root1, ptr2 = root2, ptr; 
    Node root = null, temp; 
 
    while (ptr1 != null)
    { 
        temp = new Node(); 
        temp.next = null; 
 
        // Compare for greater node 
        if (ptr1.data < ptr2.data) 
            temp.data = ptr2.data; 
        else
            temp.data = ptr1.data; 
 
        if (root == null) 
            root = temp; 
        else
        { 
            ptr = root; 
            while (ptr.next != null) 
                ptr = ptr.next; 
 
            ptr.next = temp; 
        } 
        ptr1 = ptr1.next; 
        ptr2 = ptr2.next; 
    } 
    return root; 
} 
 
static void display(Node root) 
{ 
    while (root != null) 
    { 
        Console.Write( root.data + "->"); 
        root = root.next; 
    } 
    Console.WriteLine();
} 
 
// 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); 
 
    Console.Write("First List: "); 
    display(root1); 
 
    // Second linked list 
    root2 = insert(root2, 1); 
    root2 = insert(root2, 7); 
    root2 = insert(root2, 4); 
    root2 = insert(root2, 5); 
 
    Console.Write( "Second List: "); 
    display(root2); 
 
    root = newList(root1, root2); 
    Console.Write("New List: "); 
    display(root); 
} 
}
 
// This code has been contributed by 29AjayKumar

Javascript

<script>
// javascript program to create a new linked list 
// from two given linked list 
// of the same size with 
// the greater element among the two at each node 
 
    // Representation of node
class Node {
    constructor(val) {
        this.data = val;
        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 which returns new linked list
    function newList( root1,  root2) {
        var ptr1 = root1, ptr2 = root2, ptr;
        var root = null, temp;
 
        while (ptr1 != null) {
            temp = new Node();
            temp.next = null;
 
            // Compare for greater node
            if (ptr1.data < ptr2.data)
                temp.data = ptr2.data;
            else
                temp.data = ptr1.data;
 
            if (root == null)
                root = temp;
            else {
                ptr = root;
                while (ptr.next != null)
                    ptr = ptr.next;
 
                ptr.next = temp;
            }
            ptr1 = ptr1.next;
            ptr2 = ptr2.next;
        }
        return root;
    }
 
    function display( root) {
        while (root != null) {
            document.write(root.data + "->");
            root = root.next;
        }
        document.write("<br/>");
    }
 
    // 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);
 
        document.write("First List: ");
        display(root1);
 
        // Second linked list
        root2 = insert(root2, 1);
        root2 = insert(root2, 7);
        root2 = insert(root2, 4);
        root2 = insert(root2, 5);
 
        document.write("Second List: ");
        display(root2);
 
        root = newList(root1, root2);
        document.write("New List: ");
        display(root);
 
// This code is contributed by gauravrajput1 
</script>

Output:

First List:  5->2->3->8->
Second List: 1->7->4->5->
New List:    5->7->4->8->

Time complexity: O(n) where n is size of linked list

Space complexity: O(1) since using constant space

Suggest improvement

How does Floyd's slow and fast pointers approach work?

Find N distinct numbers whose bitwise Or is equal to K

Share your thoughts in the comments

Create new linked list from two given linked list with greater element at each node

C++

Java

Python3

C#

Javascript

Please Login to comment...

Similar Reads

What kind of Experience do you want to share?