# Merge Two Sorted Lists Leetcode Solutions  Difficulty Level Easy
algorithms coding Interview interviewprep LeetCode LeetCodeSolutions Linked-List

Linked lists are quite like arrays in their linear properties. We can merge two sorted arrays to form an overall sorted array. In this problem, we have to merge two sorted linked lists in place to return a new list which contains elements of both lists in a sorted fashion.

## Example   ```L1 = 1   ->   2   ->   9
L2 = 1   ->   3   ->   4```
`1 1 2 3 4 9`

## Approach  The simplest way to do it would be to use the two-pointer technique. Create a new empty list. Append the smaller elements among both the pointers and increment the corresponding pointer. This is a good approach but requires the creation of an extra list that consumes space.

The Optimal Approach should consume constant space only in order to do an in-place sorting. We can follow the iterative approach. We already have the nodes stored in both the lists. Create a new list pointer and its subsequent “next pointers” should point to predefined nodes in the memory. In this process, we create no new nodes.

## Algorithm(Naive Approach)  1. Create a function mergeTwoSortedLists() that takes two list pointers as arguments
2. If either of the lists is NULL, return the other one
3. Create a temp variable that will point to the smaller node among heads of both lists
4. Now, at least, one node is appended to our result, so one head should be incremented
5. This creates a subproblem. So, call the same recursive function and append it to temp
6. If List1.value < List2.value
• temp = new ListNode(List1.value) , temp->next = mergeTwoSortedLists(List1->next , List2)
7. If List2.value <= List1.value
• temp = new ListNode(List2.value) , temp->next = mergeTwoSortedLists(List1 , List2->next)
8. Return temp to get the desired list
Count pair with Given Sum

## Algorithm(Optimal)  1. Create a new list pointer which will be called dummy_head.
3. The “next pointers” of dummy_head should be manipulated in such a way that it points to the predefined nodes in lists l1 and l2.
4. We can do the above task in following ways:
• Keep iterating the lists with pointers starting from their heads.
• Unless one of the lists is completely traversed:
• Append the smaller valued node from the two list pointers to the dummy_head, incrementing the corresponding pointer.
• Now, at least one of the pointers is NULL. So, append the non-null list to the dummy head.
5. Return the head of the dummy list.

## Implementation  ### C++ Program to Merge Two Sorted Lists

#### Naive Approach

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

struct listNode
{
int value;
listNode* next;

listNode(int x)
{
value = x;
next = NULL;
}
};

listNode* mergeTwoSortedLists(listNode* l1 , listNode* l2)
{
if(!l1)
return l2;
if(!l2)
return l1;

listNode* temp;
if(l1->value < l2->value)
{
temp = new listNode(l1->value);
temp->next = mergeTwoSortedLists(l1->next , l2);
}
else
{
temp = new listNode(l2->value);
temp->next = mergeTwoSortedLists(l1 , l2->next);
}

return temp;
}

{
{
cout << head->value << " ";
}
cout << '\n';
return;
}

int main()
{
listNode* l1 = new listNode(1);
l1->next = new listNode(2);
l1->next->next = new listNode(9);

listNode* l2 = new listNode(1);
l2->next = new listNode(3);
l2->next->next = new listNode(4);

print(mergeTwoSortedLists(l1 , l2));
return 0;
}
```

#### Optimal Method

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

struct listNode
{
int value;
listNode* next;

listNode(int x)
{
value = x;
next = NULL;
}
};

listNode* mergeTwoSortedLists(listNode* l1 , listNode* l2)
{
while(l1 && l2)
{
if(l1->value < l2->value)
{
l1 = l1->next;
}
else
{
l2 = l2->next;
}
}

dummy_head->next = (l1 ? l1 : l2);
}

{
{
cout << head->value << " ";
}
cout << '\n';
return;
}

int main()
{
listNode* l1 = new listNode(1);
l1->next = new listNode(2);
l1->next->next = new listNode(9);

listNode* l2 = new listNode(1);
l2->next = new listNode(3);
l2->next->next = new listNode(4);

print(mergeTwoSortedLists(l1 , l2));
return 0;
}
```
`1 1 2 3 4 9`

### Java Program to Merge Two Sorted Lists

#### Naive Approach

```class listNode
{
int value;
listNode next;

listNode(int x)
{
value = x;
next = null;
}
}

class merge_two_sorted_lists
{
{
{
}
return;
}

public static listNode mergeTwoSortedLists(listNode l1 , listNode l2)
{
if(l1 == null)
return l2;
if(l2 == null)
return l1;

listNode temp;
if(l1.value < l2.value)
{
temp = new listNode(l1.value);
temp.next = mergeTwoSortedLists(l1.next , l2);
}
else
{
temp = new listNode(l2.value);
temp.next = mergeTwoSortedLists(l1 , l2.next);
}

return temp;
}

public static void main(String args[])
{
listNode l1 = new listNode(1);
l1.next = new listNode(2);
l1.next.next = new listNode(9);

listNode l2 = new listNode(1);
l2.next = new listNode(3);
l2.next.next = new listNode(4);

print(mergeTwoSortedLists(l1 , l2));
}
}
```

#### Optimal Method

```class listNode
{
int value;
listNode next;

listNode(int x)
{
value = x;
next = null;
}
}

class merge_two_sorted_lists
{
{
{
}
return;
}

public static listNode mergeTwoSortedLists(listNode l1 , listNode l2)
{
while(l1 != null && l2 != null)
{
if(l1.value < l2.value)
{
l1 = l1.next;
}
else
{
l2 = l2.next;
}
}

dummy_head.next = ((l1 != null) ? l1 : l2);
}

public static void main(String args[])
{
listNode l1 = new listNode(1);
l1.next = new listNode(2);
l1.next.next = new listNode(9);

listNode l2 = new listNode(1);
l2.next = new listNode(3);
l2.next.next = new listNode(4);

print(mergeTwoSortedLists(l1 , l2));
}
}
```
`1 1 2 3 4 9`

## Complexity Analysis  ### Time Complexity to Merge Two Sorted Lists

O(N + M), where N and M are the lengths of the two lists. We traverse both the lists once in both approaches, so both the algorithms are linear.