### Introduction

The linked list is one of the most important concepts and data structures to learn while preparing for interviews. Having a good grasp of Linked Lists can be a huge plus point in a coding interview.

### Problem Statement

In this problem, we will be given two sorted linked lists. We need to merge both lists such that the newly created list is also in sorted order.

### Problem Statement Understanding

The problem statement is quite straightforward, we will get two linked lists that are sorted in nature, and then we need to form a linked list using all the nodes of both linked lists such that the newly formed list is sorted in order.

**Note:** Remember that we cannot use any extra space, as we need to do this in place.

Let’s try to understand it more clearly using examples.

Let the two sorted lists given to us be:

- Now, the list that we need to return must contain all the nodes of both lists in sorted order.
- So, the newly formed list should be:

Let’s take another example:

Let the two sorted lists given to us be 2→8→9→10→NULL and 11→13→17→NULL

- For the above two sorted lists, the final linked list after merging will be 2→8→9→10→11→13→17→NULL

##### Some more examples

Sample Input 1:

- list 1: 1→2→5→10→NULL
- list 2: 3→7→9→11→NULL

Sample Output 1: 1→2→3→5→7→9→10→11→NULL

Sample Input 2:

- list 1: 2→3→9→10→NULL
- list 2: 4→5→7→8→12→NULL

Sample Output 2: 2→3→4→5→7→8→9→10→12→NULL

At this point, we have understood the problem statement. Now we will try to formulate an approach for this problem.

- Before moving to the approach section, try to think about how you can approach this problem.

If stuck, no problem, we will thoroughly see how we can approach this problem in the next section.

Let’s move to the approach section.

### Approach 1

Our approach will be simple:

- We will make a recursive function that will create a sorted list out of two given sorted lists.
- If both the heads of the linked lists are NULL, return NULL and if only one head is NULL, then return the other head.
- We will compare the head of both the lists and the one with a smaller head will be appearing at the current position and all other nodes will appear after that.
- Now call the recursive function again with parameters as the next node of the list having a smaller head value and the head of the other list.
- Our recursive call will be returning the next smaller element of the linked lists attached with the rest of the sorted list. Make next of current node point to the list returned by the recursive function
**(curr_node->next = recursiveFunction())**.

Following all the above steps, we will have our merged sorted list containing nodes of all the given linked list in sorted order.

### Algorithm 1

1) The recursive function will have two parameters, i.e., **head1** and **head2**, denoting the current head node of the **first** and **second list**, respectively.

2) Base case:

- If both of the head nodes are NULL, return NULL from there.
- If one of the head nodes is NULL, but the other one is not NULL, return the other head.

3) If**head1’s data**is less than**head2’s data**, assign**head1’s next**to the result returned by the recursive function having parameters**head1→next**and**head2**and then return**head1**.

4) Else, assign**head2’s next**to the result returned by the recursive function having parameters**head1**and**head2→next**and then return**head2**.

**Time Complexity:** O(n), n is the number of nodes in both the list combined.

**Space Complexity:** O(n), n is the size of the recursive stack

The above approach works fine, but can we make our code more efficient in memory.

- The answer is yes, and to know it, have a look at the helpful observations and also read the below approach which uses constant memory.

#### Helpful Observations

- If we observe, we can see that we need two pointers at the beginning of both the list, since the smallest value will be present at the beginning of both the lists.
- The list has a smaller first node that will be considered as the first list and the other one would be considered the second list.
- We then have to just insert the second pointer node between the first and its next node if its value lies between the first and its next node.
- If that is not the case, then we just need to move forward in iteration.

Applying the above observations, we can easily create the new sorted linked list.

### Approach 2

Taking help from the observation explained above, let us understand the approach with the help of an example.

- Let the input lists be 1→4→7→10→NULL and 2→3→22→NULL
- We would keep two pointers – one at the starting of each linked list.
- Now, the first pointer will point to ‘1’ because the first list has a smaller first node, and the second one will point to ‘2’ because it has a greater first node.
- Since the second pointer’s data lies between ‘1’ and ‘4’ (first pointer’s data and next of first pointer’s data), so we insert it between ‘1’ and ‘4’.
- After inserting the second node, we update the head of the second list to its next node.
- Now let’s suppose the value of the second pointer was greater than ‘4’ so, we would not do anything in this case and just move our first pointer forward by one node.

Now, let’s formulate an algorithm based on the approach discussed above and handle the edge cases that might be present while implementing the code.

### Algorithm 2

- Find which list has a smaller first node and consider it as the first list and the other one as the second list (
**flist**stands for**first list**and**slist**stands for**second list**). - Now, initialize four pointers:
- First will point to the head of the first list ( say
**flist_curr**). - The second will point to the second node of the first list ( say
**flist_next**). - The third will point to the head of the second list ( say
**slist_curr**). - The Fourth will point to the second node of the second list ( say
**slist_next**).

- First will point to the head of the first list ( say
- While iterating through the lists, we need to check if
**slist_curr’s value**lies between**flist_curr’s value**and**flist_next’s value**.

a) If its value lies in between, then we need to insert the**slist_curr**node in between**flist_curr**and**flist_next**and update**flist_curr**to**slist_curr**and**slist_curr**to**slist_next**.

b) Else, we will check if there are more nodes in the first list.- If there are more nodes in the first list, then just move
**flist_curr**and**flist_next**to their respective next nodes. - If that is not the case, then the last node of the first node should point to the remaining nodes of the second list, and then finally, we will return the head of the first list.

- If there are more nodes in the first list, then just move
- After performing the above steps, we would get our new list that is sorted.

### Dry Run

### Code Implementation

#include <stdio.h> #include<stdbool.h> #include<stdlib.h> struct Node { int data; struct Node* prev; struct Node* next; }; void push(struct Node **head_ref, int data) { struct Node* ptr1 = (struct Node*) malloc(sizeof(struct Node)); struct Node *temp = *head_ref; ptr1->data = data; ptr1->next = *head_ref; if (*head_ref != NULL) { while (temp->next != *head_ref) temp = temp->next; temp->next = ptr1; } else ptr1->next = ptr1; *head_ref = ptr1; } void printList(struct Node *head) { struct Node *temp = head; if (head != NULL) { do { printf("%d ",temp->data); temp = temp->next; } while (temp != head); } } int main(void) { struct Node *head = NULL; push(&head, 15); push(&head, 18); push(&head, 7); push(&head, 1); printf( "Contents of Circular Linked List\n "); printList(head); }

#include<bits/stdc++.h> using namespace std; class Node { public: int data; Node* next; Node(int x){ data = x; next = NULL; } }; void printList(Node *head) { if (!head) return; while (head->next != NULL) { cout << head->data << " -> "; head = head->next; } cout << head->data << endl; } Node* mergeTwoSortedLists(Node* head1, Node* head2) { // if first list has only one node if (!head1->next) { head1->next = head2; return head1; } // make the list with smaller first node as first list if((head1->data) > (head2->data)){ Node *temp = head1; head1 = head2; head2 = temp; } // Initialize all four pointer as discussed above in step 1 Node *flist_curr = head1, *flist_next = head1->next; Node *slist_curr = head2, *slist_next = head2->next; while (flist_next && slist_curr) { // if value of slist_curr lies in between value of flist_curr and // value of flist_next then insert slist_curr between flist_curr and // flist_next if ((slist_curr->data) >= (flist_curr->data) && (slist_curr->data) <= (flist_next->data)) { slist_next = slist_curr->next; flist_curr->next = slist_curr; slist_curr->next = flist_next; // update flist_curr to point to slist_curr and slist_curr to point to slist_next flist_curr = slist_curr; slist_curr = slist_next; } else { // if we have not reached end of first list if (flist_next->next) { flist_next = flist_next->next; flist_curr = flist_curr->next; } // if we have reached the end of the first list then // point last node’s next to remaining nodes of // second list else { flist_next->next = slist_curr; return head1; } } } return head1; } int main(void) { Node* head1 = NULL; head1 = new Node(1); head1->next = new Node(4); head1->next->next = new Node(7); head1->next->next->next = new Node(10); Node* head2 = NULL; head2 = new Node(2); head2->next = new Node(3); head2->next->next = new Node(22); Node *tmp = mergeTwoSortedLists(head1,head2); cout<<"Merged Linked list"<<endl; printList(tmp); return 0; }

class MergeInPlace { static class Node { int data; Node next; } static Node newNode(int key) { Node temp = new Node(); temp.data = key; temp.next = null; return temp; } static void printList(Node node) { while (node != null) { System.out.print(node.data + " "); node = node.next; } } // Merges two lists with headers as h1 and h2. // It assumes that h1's data is smaller than // or equal to h2's data. static Node mergeUtil(Node h1, Node h2) { // if only one node in first list // simply point its head to second list if (h1.next == null) { h1.next = h2; return h1; } // Initialize current and next pointers of // both lists Node curr1 = h1, next1 = h1.next; Node curr2 = h2, next2 = h2.next; while (next1 != null && curr2 != null) { // if curr2 lies in between curr1 and next1 // then do curr1->curr2->next1 if ((curr2.data) >= (curr1.data) && (curr2.data) <= (next1.data)) { next2 = curr2.next; curr1.next = curr2; curr2.next = next1; // now let curr1 and curr2 to point // to their immediate next pointers curr1 = curr2; curr2 = next2; } else { // if more nodes in first list if (next1.next != null) { next1 = next1.next; curr1 = curr1.next; } // else point the last node of first list // to the remaining nodes of second list else { next1.next = curr2; return h1; } } } return h1; } // Merges two given lists in-place. This function // mainly compares head nodes and calls mergeUtil() static Node merge(Node h1, Node h2) { if (h1 == null) return h2; if (h2 == null) return h1; // start with the linked list // whose head data is the least if (h1.data < h2.data) return mergeUtil(h1, h2); else return mergeUtil(h2, h1); } // Driver code public static void main(String[] args) { Node head1 = newNode(1); head1.next = newNode(3); head1.next.next = newNode(5); // 1->3->5 LinkedList created Node head2 = newNode(0); head2.next = newNode(2); head2.next.next = newNode(4); // 0->2->4 LinkedList created Node mergedhead = merge(head1, head2); printList(mergedhead); } }

class Node: def __init__(self, data): self.data = data self.next = None def newNode(key): temp = Node(0) temp.data = key temp.next = None return temp def printList(node): while (node != None) : print( node.data, end =" ") node = node.next def mergeUtil(h1, h2): if (h1.next == None) : h1.next = h2 return h1 curr1 = h1 next1 = h1.next curr2 = h2 next2 = h2.next while (next1 != None and curr2 != None): if ((curr2.data) >= (curr1.data) and (curr2.data) <= (next1.data)) : next2 = curr2.next curr1.next = curr2 curr2.next = next1 curr1 = curr2 curr2 = next2 else : if (next1.next) : next1 = next1.next curr1 = curr1.next else : next1.next = curr2 return h1 return h1 def merge( h1, h2): if (h1 == None): return h2 if (h2 == None): return h1 if (h1.data < h2.data): return mergeUtil(h1, h2) else: return mergeUtil(h2, h1) head1 = newNode(1) head1.next = newNode(4) head1.next.next = newNode(7) head1.next.next.next = newNode(10) head2 = newNode(2) head2.next = newNode(3) head2.next.next = newNode(22) mergedhead = merge(head1, head2) print("Merged Linked list") printList(mergedhead)

#### Output

Merged Linked list

1 -> 2 -> 3 -> 4 -> 7 -> 10 -> 22

**Time Complexity:** O(n), where n is the number of nodes in the list.

[forminator_quiz id=”5162″]

So, in this blog, we have tried to explain how you can merge two sorted linked lists (in-place) in the most optimal way. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.