×

Search anything:

# Merge two sorted linked lists

Indian Technical Authorship Contest starts on 1st July 2023. Stay tuned.

In this article, we will learn how to Merge two sorted linked list such that the final linked list is also sorted in linear time O(N).

1. Problem Statement: Merge two sorted linked lists
2. Algorithm
3. Implementation (Step by Step)

Let us get started with Merge two sorted linked lists.

# Problem Statement: Merge two sorted linked lists

Merge two given sorted linked list and return head of new linked list which should also be sorted.

### Example :

Input: linked list 1 = {1,2,4} , linked list 2 = {1,3,4}
Output: {1,1,2,3,4,4}

# Time Complexity :

O(n), beacuse of only one loop iterating only one time.

# Algorithm

The steps to Merge two sorted linked lists are:

• Traverse both Linked Lists linearly from the first node
• Compare current nodes of both Linked List
• Delete the smaller node
• Insert the smaller node at the end of final Linked List
• If one Linked List is empty during processing, move all elements of the other sorted Linked List to the end of the final Linked List

The implementation steps are:

1.First we define a node by either using struct or class.
2.Create a function to create new nodes.
3.Create a function which takes two sorted linked lists as input and return head of merged linkedlist.
4.Create a function to display the linked list and write main function.

# Implementation (Step by Step)

## Step 1 : Defining a node

We can do this by either using struct or class.

``````   struct node{
int data;
struct node* next;
};
``````

or

``````   class node{
public:
int data;
node* next;
};
``````

## Step 2 : Function to create a new node

``````  node* newnode(int key)
{
struct node* temp = new node;
temp->data = key;
temp->next = NULL;
return temp;
}
``````

## Step 3 : Function to merge sorted linked lists

### Approach :

1. Check if linked list 1 is empty return linked list 2 , or if linked list 2 is empty return linked list 1.

2. Create new head of the merged linked list by comparing both linked list first elements and choosing the smaller value beacuse we want to maintain the order (should be sorted).

3. Now, for rest of the elements compare them one by one in a while loop and maintain a new pointer which will keep storing the elements and thus a new sorted linked list will be formed.

4. In the end just check if any element is left in the linked lists, if yes then add them to the new merged linked list and return head of new linked list.

### Working of Code :

Let us take an example :-

List 1 = 1 -> 2 -> 4
List 2 = 1 -> 3 -> 5
final_list = null

Compare first two nodes in both linked lists : `[1,1]` both are equal we can choose to add any of the two in the final_list and move head pointer of the choosen list, in this case we choose list 1 and move head pointer to next element

List 1 = 2 -> 4
List 2 = 1 -> 3 -> 5
final_list = 1

Compare first two nodes in both linked lists : `[2,1]` , 1 is smaller so add it to the final_list and move the pointer in list 2.

List 1 = 2 -> 4
List 2 = 3 -> 5
final_list = 1 -> 1

Compare the first two nodes in both linked lists : `[2,3]`, 2 is smaller so add it to the final_list and move the pointer in list 1.

List 1 = 4
List 2 = 3 -> 5
final_list = 1 -> 1 -> 2

Compare the first two nodes in both linked lists : `[4,3]`, 3 is smaller so add it to the final_list and move the pointer in list 2.

List 1 = 4
List 2 = 5
final_list = 1 -> 1 -> 2 -> 3

Compare the last two nodes in both linked lists : `[4,5]`, 4 is smaller so add it to the final_list and move the pointer in list 1.

List 1 = NULL
List 2 = 5
final_list = 1 -> 1 -> 2 -> 3 -> 4

If any one of the two linked lists is pointing to NULL then simply add all the elements of other list in final_list.

final_list = 1 -> 1 -> 2 -> 3 -> 4 -> 5

### Note :

We are not deleting the elements of the two linked lists, but as we move the head pointer to the next element in linked list we already lost the previous element because we now don't have any means to go back to previous element, remember in a singly linked list only the address of next element is stored but not the previous one.

### Implementation :

``````   //function takes two linked lists as input

//Check if any linked list is empty
} else if (head2 == nullptr) {
}

//check for smallest element by comparing first two elements

//moving head 1 to point to next element in the
//linked list 1 for further comparison

} else {

//moving head 2 to point to next element in the
//linked list 2 for further comparison

}

//new pointer to move forward and store new elements and

//run the loop until we reach last element of both lists
node* temp = nullptr;
} else {
}

//store the next element and move forward to new node
}

//if any element is left then add it to final linked list
} else if (head2 != nullptr) {
}

}
``````

## Step 4 : Main function and Display function

1. Write a main function to call the merged_linkedlist function.
2. Wrtie a display function to print merged linked list.
``````   void display(node* node1)
{
while (node1 != NULL) {
printf("%d  ", node1->data);
node1 = node1->next;
}
}

int main()
{

//call merging function

return 0;
}
``````

## Final Code :

``````   #include<bits/stdc++.h>
using namespace std;
//defining node type using struct
struct node{
int data;
struct node* next;
};

//function to create new node
node* newnode(int key)
{
struct node* temp = new node;
temp->data = key;
temp->next =nullptr;
return temp;
}

//Check if any linked list is empty
} else if (head2 == nullptr) {
}

//check for smallest element by comparing first two elements

//moving head 1 to point to next element in the
//linked list 1 for further comparison

} else {

//moving head 2 to point to next element in the
//linked list 2 for further comparison

}

//new pointer to move forward and store new elements and

//run the loop until we reach last element of both lists
node* temp = nullptr;
} else {
}

//store the next element and move forward to new node
}

//if any element is left then add it to final linked list
} else if (head2 != nullptr) {
}

}

void display(node* node1)
{

while (node1 != nullptr) {
cout<<node1->data<<" ";
node1 = node1->next;
}
cout<<endl;

}

int main()
{

return 0;
}
``````

## Output :

``````   linked list 1 - 1 3 5
linked list 2 - 0 2 4
merged linked list - 0 1 2 3 4 5
``````

With this article at OpenGenus, you must have the complete idea of approaches to Merge two sorted linked lists.

#### Kartik Keyan Kant

B. Tech | CSE | 3rd year | C++ | Java | C | AI | Bangalore | inbuilt function __learning( )