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

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*/

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

/* Driver function*/
int main() {

/* Initializing an empty Linked List*/

/* Inserting Sample elements for list1*/

/* Inserting Sample elements for list2*/

/* Displaying elements of given lists*/
cout << "The given sorted lists are:\nList1 : " ;
cout<<"\nList2 : ";
cout<<"\n";

/* Initializing an empty list */

/* Temporary variables for reference*/

/* 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){
temp1 = temp1->next;
}
else{
temp2 = temp2->next;
}
}

/* To insert the remaining elements of list1 */
while(temp1 != NULL){
temp1 = temp1->next;
}

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

/* Displaying elements of the final merged list*/
cout<<"Merged list: ";
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 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.