Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem 
2.1.
Example
2.1.1.
Input
2.1.2.
Output
3.
Solution Approach 
3.1.
C++ Implementation
3.1.1.
Output
3.2.
Complexity 
3.2.1.
Time complexity 
3.2.2.
Auxiliary Space complexity
4.
FAQs
4.1.
What is a Linked List?
4.2.
How is a Linked list different from an array?
4.3.
Is random access possible on the Linked list?
4.4.
What are the different types of Linked lists available?
4.5.
What is a struct data type in C++?
5.
Conclusion
Last Updated: Mar 27, 2024

Create a List in Reverse Order by Merging Two Sorted Linked List

Author Teesha Goyal
1 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

A Linked List is a container, a data structure that stores the elements at non-contiguous memory locations. Each node has a next pointer that holds the address of the next node, which is used to traverse the list. To learn more about Linked List, visit our site, Linked List | Learn & Practice from Coding Ninjas Studio

Problem 

We are given two sorted linked lists, and we need to create a list in reverse order by merging two sorted linked lists. The given lists are sorted in ascending order, and the final list should be in descending order. 

Example

Input

List1 = 2 -> 4 -> 6 -> 8 -> 10

List2 =  1 -> 3 -> 5

Output

Merged_list = 10 -> 8 -> 6 -> 5 -> 4 ->  3 -> 2 -> 1

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Solution Approach 

There are two methods in which you can solve the above problem 

  1. The simple solution to the problem is pretty straightforward. Merge the given two sorted linked lists and then sort the merged list in descending order. 
  2. Reverse the given lists and merge them by checking the larger element each time adding an item.

Both these solutions require two traversals of the linked list. 

A better solution is to initialize an empty list. Traverse the two given lists, compare the current node of both lists, add the smaller node to the merged list, and continue until one of the lists ends. Add the remaining nodes to the merged list. 

The steps of implementation are: 

  1. Take two sorted linked lists. 
     
  2. Initialize the merge list as an empty linked list.
     
  3. Loop over to add the smaller element from the two lists and continue till one of the lists ends. 
     
  4. Write separate loops to add the remaining elements from the lists to the merged list.
     
  5. Create a DisplayLinkedlist method to print the linked list on the terminal.

C++ Implementation

#include<iostream>
using namespace std;
 
/* Declaring Struct variable Node to represent a node in the Linked List. */
struct Node {
    int data;
    Node *next;
};
 
/* A function to display the given linekd list*/
void DisplayLinkedList(Node *node) {
   
    /* Loop to iterate over the list and printing each element*/
    while (node != NULL) {
        cout << node->data;
        node = node->next;
       
        if(node != NULL)
            cout<<" -> ";
    }
}
 
/* An insert function to insert an item with value temp_data in the Linked list*/
void NodeInsert(Node** head_ref, int temp_data) {
    Node* temp_node = new Node();
    temp_node->data = temp_data;
    temp_node->next = (*head_ref);
    (*head_ref) = temp_node;
}
 
/* Driver function*/
int main() {
   
    /* Initializing an empty Linked List*/
    Node* head1 = NULL;
    Node* head2 = NULL;
   
    /* Inserting Sample elements for list1*/
    NodeInsert(&head1, 10);
    NodeInsert(&head1, 8);
    NodeInsert(&head1, 7);
    NodeInsert(&head1, 5);
    NodeInsert(&head1, 3);
   
    /* Inserting Sample elements for list2*/
    NodeInsert(&head2, 9);
    NodeInsert(&head2, 6);
    NodeInsert(&head2, 4);
    NodeInsert(&head2, 2);
    NodeInsert(&head2, 1);
   
    /* Displaying elements of given lists*/
    cout << "The given sorted lists are:\nList1 : " ;
    DisplayLinkedList(head1);
    cout<<"\nList2 : ";
    DisplayLinkedList(head2);
    cout<<"\n";
   
    /* Initializing an empty list */
    Node* head3 = NULL;

    /* Temporary variables for reference*/
    Node* temp1 = head1;
    Node* temp2 = head2;
   
    /* Loop over the two lists two merge the lists in reverse order*/
    while(temp1 != NULL && temp2 != NULL)
    {        
        /* If the element of list1 is smaller*/
        if(temp1->data <= temp2->data){
            NodeInsert(&head3, temp1->data);
            temp1 = temp1->next;
        }
        else{
            NodeInsert(&head3, temp2->data);
            temp2 = temp2->next;
        }
    }
   
    /* To insert the remaining elements of list1 */
    while(temp1 != NULL){
        NodeInsert(&head3, temp1->data);
        temp1 = temp1->next;
    }

    /* To insert the remaining elements of list2 */
    while(temp2 != NULL){
        NodeInsert(&head3, temp2->data);
        temp2 = temp2->next;
    }

    /* Displaying elements of the final merged list*/
    cout<<"Merged list: ";
    DisplayLinkedList(head3);
    return 0;
}

Output

The given sorted lists are:
List1 : 3 -> 5 -> 7 -> 8 -> 10
List2 : 1 -> 2 -> 4 -> 6 -> 9
Merged list: 10 -> 9 -> 8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1

Complexity 

Time complexity 

O(n), where n is the sum of elements of list1 and list2.

Reason: We are traversing both the elements together in a single loop. Hence we are running the loop for n times.

Auxiliary Space complexity

O(1), constant time.

Reason: We are not creating additional lists other than the input and output. All the variables declared are fixed size that is constant.

Check out this array problem - Merge 2 Sorted Arrays

FAQs

What is a Linked List?

A Linked List is a container, a data structure that stores the elements at non-contiguous memory locations. Each node has a next pointer that holds the address of the next node. 

How is a Linked list different from an array?

A Linked list has elements stored at non-contiguous memory locations and uses the next pointer to determine the address of the next element. Whereas the array stores the elements in contiguous memory locations.

Is random access possible on the Linked list?

Unlike an array, the random access of elements is not possible in a Linked list in O(1). We have to iterate through the list to access the elements as the elements are not continuously stored.

What are the different types of Linked lists available?

There are four types of Linked lists. The different kinds of Linked lists include Singly Linked list, Doubly Linked list, Circular Linked List, and Circular Doubly Linked list.

What is a struct data type in C++?

Struct is a data type present in C++. A struct is a collection of different nodes wrapped into a single unit. A user can define a struct variable as their choice and store different data types under a single struct variable. 

Conclusion

In this article, we discussed the problem of merging two sorted linked lists such that the merge list is in reverse order. To learn more about Linked List, visit, Linked List.

Hope you would have gained a better understanding of these topics now!

Are you planning to ace the interviews of reputed product-based companies like AmazonGoogleMicrosoft, and more? 

Attempt our Online Mock Test Series on Coding Ninjas Studio now!

Happy Coding!

Previous article
Add Two Numbers Represented by the Linked Lists | Part-3
Next article
Design Browser History
Live masterclass