# Merge Two Sorted Linked Lists

Difficulty Level Easy

In merge two sorted linked lists we have given head pointer of two linked lists, merge them such that a single linked list is obtained which has nodes with values in sorted order. return the head pointer of the merged linked list.

Note: merge the linked list in-place without using any extra space.

## Example

Input Output 1. Recursive
2. Iterative

## Recursive

### Approach for Merge Two Sorted Linked Lists

The idea is to recursively merge the two input linked list such that the sorted order in the merged linked list is maintained.

### Algorithm

1. Define the base case: if any of the linked lists is empty, simply return the other.
2. Now compare data values of head nodes of both the linked lists (x and y):
• if x.data < y.data => x.next = recurse{x.next,y}.
• Else => y.next = recurse{x,y.next}.   ### Implementation

#### C++ program

```#include <iostream>
#include <bits/stdc++.h>
using namespace std;

/* blue print of node */
class Node
{
public:
int data;
Node *next;

Node(int num)
{
data = num;
next = NULL;
}
};

/* append a node at the end of the Linked List */
{
else
{
while(temp->next != NULL)
temp = temp->next;

temp->next = new Node(data);
}

}

/* print the Linked List */
{
{
}
}

/* function that merges 2 Linked Lists keeping the Sorted
Order & returns the head of of the merged Linked List */
Node *sortedMerge(Node* x,Node* y)
{
if(x == NULL)
return y;

if(y == NULL)
return x;

if(x->data < y->data)
{
x->next = sortedMerge(x->next,y);
return x;
}
else
{
y->next = sortedMerge(x,y->next);
return y;
}
}

/* function to implement above */
int main()
{
Node *x = NULL, *y = NULL;

/* construct the first Linked List */
x = insert(x,3);
x = insert(x,4);
x = insert(x,7);
x = insert(x,9);
print(x);

cout<<endl;

/* construct the second Linked List */
y = insert(y,1);
y = insert(y,2);
y = insert(y,5);
y = insert(y,6);
y = insert(y,8);
print(y);

cout<<endl;

/* merge the 2 Linked Lists and print */
cout<<"Merged Linked List in Sorted Order : ";
Node *result = sortedMerge(x,y);
print(result);

return 0;
}```
```First Linked List : 3 4 7 9
Second Linked List : 1 2 5 6 8
Merged Linked List in Sorted Order : 1 2 3 4 5 6 7 8 9```

#### Java Program

```import java.util.*;
import java.io.*;

class TutorialCup
{
/* blue print of node */
static class Node
{
int data;
Node next;

Node(int num)
{
data = num;
next = null;
}
};

/* append a node at the end of the Linked List */
{
else
{
while(temp.next != null)
temp = temp.next;

temp.next = new Node(data);
}

}

/* print the Linked List */
{
{
}
}

/* function that merges 2 Linked Lists keeping the Sorted
Order & returns the head of of the merged Linked List */
static Node sortedMerge(Node x,Node y)
{
if(x == null)
return y;

if(y == null)
return x;

if(x.data < y.data)
{
x.next = sortedMerge(x.next,y);
return x;
}
else
{
y.next = sortedMerge(x,y.next);
return y;
}
}

/* function to implement above */
public static void main (String[] args)
{
Node x = null, y = null;

/* construct the first Linked List */
x = insert(x,3);
x = insert(x,4);
x = insert(x,7);
x = insert(x,9);
print(x);

System.out.println();

/* construct the second Linked List */
y = insert(y,1);
y = insert(y,2);
y = insert(y,5);
y = insert(y,6);
y = insert(y,8);
print(y);

System.out.println();

/* merge the 2 Linked Lists and print */
System.out.print("Merged Linked List in Sorted Order : ");
Node result = sortedMerge(x,y);
print(result);
}
}```
```First Linked List : 3 4 7 9
Second Linked List : 1 2 5 6 8
Merged Linked List in Sorted Order : 1 2 3 4 5 6 7 8 9```

### Complexity Analysis

1. Time Complexity: T(n) = O(a+b).
2. Space Complexity: A(n) = O(1)

a = size of the first linked list.

b = size of the second linked list.

## Iterative

### Approach for Merge Two Sorted Linked Lists

The idea is to convert recursive code into an iterative one.

### Algorithm

1. creates two node pointers head and tail.
2. assign head.next = new Node(-1), allocating dummy node to head so that it becomes easy to merge both the linked list. the head pointer is used to retain the head of the merged linked list.
3. the tail is used to store the end of the merged linked list, the tail pointer is used append nodes from x and y at the end of the merged list.
4. Traverse both the input lists x and y simultaneously until reaching the end of one of them.
5. For each node of x and y consider:
1. if x.data < y.data => tail.next = x and move to next node in list x.
2. Else tail.next = y and move to the next node in list y.
6. If during traversal any of the list x or y becomes empty, simply append the nonempty list to the merged list.
7. In the end return head.next.       ### Implementation

#### C++ program

```#include <iostream>
#include <bits/stdc++.h>
using namespace std;

/* blue print of node */
class Node
{
public:
int data;
Node *next;

Node(int num)
{
data = num;
next = NULL;
}
};

/* append a node at the end of the Linked List */
{
else
{
while(temp->next != NULL)
temp = temp->next;

temp->next = new Node(data);
}

}

/* print the Linked List */
{
{
}
}

/* function that merges 2 Linked Lists keeping the Sorted
Order & returns the head of of the merged Linked List */
Node* utility(Node* x,Node* y)
{
/* tail is used to append a node at end
of the merged linked list at each step */

/* process until one of the linked list becomes empty */
while(x && y)
{
if(x->data < y->data)
{
tail->next = x;
x = x->next;
}
else
{
tail->next = y;
y = y->next;
}

tail = tail->next;
}

/* if any of the linked list gets exhausted
append the other one to the merged list */
if(x == NULL)
tail->next = y;

if(y == NULL)
tail->next = x;

}

/* function to merge two sorted linked
lists using a utility function */
Node *sortedMerge(Node* x,Node* y)
{
if (x == NULL)
return y;
if (y == NULL)
return x;

if (x->data < y->data)
return utility(x,y);
else
return utility(y,x);
}

/* function to implement above */
int main()
{
Node *x = NULL, *y = NULL;

/* construct the first Linked List */
x = insert(x,3);
x = insert(x,4);
x = insert(x,7);
x = insert(x,9);
print(x);

cout<<endl;

/* construct the second Linked List */
y = insert(y,1);
y = insert(y,2);
y = insert(y,5);
y = insert(y,6);
y = insert(y,8);
print(y);

cout<<endl;

/* merge the 2 Linked Lists and print */
cout<<"Merged Linked List in Sorted Order : ";
Node *result = sortedMerge(x,y);
print(result);

return 0;
}```
```First Linked List : 3 4 7 9
Second Linked List : 1 2 5 6 8
Merged Linked List in Sorted Order : 1 2 3 4 5 6 7 8 9```

#### Java Program

```import java.util.*;
import java.io.*;

class TutorialCup
{
/* blue print of node */
static class Node
{
int data;
Node next;

Node(int num)
{
data = num;
next = null;
}
};

/* append a node at the end of the Linked List */
{
else
{
while(temp.next != null)
temp = temp.next;

temp.next = new Node(data);
}

}

/* print the Linked List */
{
{
}
}

/* function that merges 2 Linked Lists keeping the Sorted
Order & returns the head of of the merged Linked List */
static Node utility(Node x,Node y)
{
/* tail is used to append a node at end
of the merged linked list at each step */

/* process until one of the linked list becomes empty */
while(x != null && y != null)
{
if(x.data < y.data)
{
tail.next = x;
x = x.next;
}
else
{
tail.next = y;
y = y.next;
}

tail = tail.next;
}

/* if any of the linked list gets exhausted
append the other one to the merged list */
if(x == null)
tail.next = y;

if(y == null)
tail.next = x;

}

/* function to merge two sorted linked
lists using a utility function */
static Node sortedMerge(Node x,Node y)
{
if (x == null)
return y;
if (y == null)
return x;

if (x.data < y.data)
return utility(x,y);
else
return utility(y,x);
}

/* function to implement above */
public static void main (String[] args)
{
Node x = null, y = null;

/* construct the first Linked List */
x = insert(x,3);
x = insert(x,4);
x = insert(x,7);
x = insert(x,9);
print(x);

System.out.println();

/* construct the second Linked List */
y = insert(y,1);
y = insert(y,2);
y = insert(y,5);
y = insert(y,6);
y = insert(y,8);
print(y);

System.out.println();

/* merge the 2 Linked Lists and print */
System.out.print("Merged Linked List in Sorted Order : ");
Node result = sortedMerge(x,y);
print(result);
}
}```
```First Linked List : 3 4 7 9
Second Linked List : 1 2 5 6 8
Merged Linked List in Sorted Order : 1 2 3 4 5 6 7 8 9```

### Complexity Analysis

1. Time Complexity: T(n) = O(a+b).
2. Space Complexity: A(n) = O(1), head and tail pointers are used which take constant memory.

a = size of the first linked list.

b = size of the second linked list.

References

Translate »