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

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;
}

You can also try this code with Online C++ Compiler

Run Code

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

You can also try this code with Online C++ Compiler

Run Code

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 Amazon, Google, Microsoft, and more? 

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

Happy Coding!