# 10) Merge Two Sorted Lists

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

Example:

```Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4```

## Explanation

``````

L1 = 1->4

L2 = 2->3

Output = 1->2->3->4

Create a dummy node.
ListNode dummy = new ListNode(0);
//dummy = 0->null;

Assign the dummy node to head

//iteration first time
while(l1 != null && l2 != null)
{
int val1 = l1.val;
int val2 = l2.val;

//val1 = 1
//val2 = 2

Since val1 < val2, it satisfies the first condition
if(val1 <= val2)
{
ListNode newNode = new ListNode(val1);
//newNode = 1->null

l1 = l1.next;
//iterate the l1 (l1 = l1.next)
//now the l1 holds the 4->null
}
else
{ ...
}

//now head moves to the 1->null
}

//iteration second time
while(l1 != null && l2 != null)
{
int val1 = l1.val;
int val2 = l2.val;

//val1 = 4
//val2 = 2

Since val1 > val2, it does not satisfies the first condition, it satisfies the else condition
if(val1 <= val2)
{
ListNode newNode = new ListNode(val1);

l1 = l1.next;
}
else
{
ListNode newNode = new ListNode(val2);
//newNode = 2->null

l2 = l2.next;
//l2 = 3->null
}

//now head moves to the 2->null
}

//iteration third time
while(l1 != null && l2 != null)
{
int val1 = l1.val;
int val2 = l2.val;

//val1 = 4
//val2 = 3

Since val1 > val2, it does not satisfies the first condition, it satisfies the else condition
if(val1 <= val2)
{
ListNode newNode = new ListNode(val1);

l1 = l1.next;
}
else
{
ListNode newNode = new ListNode(val2);
//newNode = 3->null

l2 = l2.next;
//l2 = null
}

//now head moves to the 2->null
}

Since l2 is null, it comes out of the while loop
Still now we have,
l1 = 4->null;
Important Note : head is standing in the 3->null

if(l1 == null) //since l1 is not null now, it will not satisfy this condition, it moves into else part
else

Note:
head pointer points to the 4->null;

so when i return dummy.next - it will return 1-2->3->4->null;

Here, we solved this problem.``````

## Program

### Provided Code

```class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
}
}```

### Solution

```class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode sentinel = new ListNode(0);
while(l1 != null && l2 != null)
{
int val1 = l1.val;
int val2 = l2.val;

if(val1 <= val2)
{
ListNode newNode = new ListNode(val1);
l1 = l1.next;
}
else
{
ListNode newNode = new ListNode(val2);
l2 = l2.next;
}

}
if(l1 == null)