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->4Output: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
ListNode head = dumy;
//head = 0->null
//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
head.next = newNode;
//put this newNode into head.next,
//head = 0->1->null
l1 = l1.next;
//iterate the l1 (l1 = l1.next)
//now the l1 holds the 4->null
}
else
{ ...
}
head = head.next;
//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);
head.next = newNode;
l1 = l1.next;
}
else
{
ListNode newNode = new ListNode(val2);
//newNode = 2->null
head.next = newNode;
//head = 0->1->2->null
l2 = l2.next;
//l2 = 3->null
}
head = head.next;
//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);
head.next = newNode;
l1 = l1.next;
}
else
{
ListNode newNode = new ListNode(val2);
//newNode = 3->null
head.next = newNode;
//head = 0->1->2-3>null
l2 = l2.next;
//l2 = null
}
head = head.next;
//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;
head = 0->1->2->3->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
head.next = l2.next;
else
head.next = l1;
//head = 0->1->2->3->4-null;
Note:
head = 0->1->2->3->4->null;
head pointer points to the 4->null;
We already have dummy node pointer, it is already refering to the headth 0->... node,
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); ListNode head = sentinel; while(l1 != null && l2 != null) { int val1 = l1.val; int val2 = l2.val; if(val1 <= val2) { ListNode newNode = new ListNode(val1); head.next = newNode; l1 = l1.next; } else { ListNode newNode = new ListNode(val2); head.next = newNode; l2 = l2.next; } head = head.next; } if(l1 == null) head.next = l2; else head.next = l1; return sentinel.next; } }

Time Complexity : O(n + m)

Space Complexity : O(1)