# LeetCode - Merge Two Sorted Lists

### Problem statement

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

Problem statement taken from: https://leetcode.com/problems/merge-two-sorted-lists

Example 1:

``````Input: l1 = [1, 2, 4], l2 = [1, 3, 4]
Output: [1, 1, 2, 3, 4, 4]``````

Example 2:

``````Input: l1 = [], l2 = []
Output: []``````

Example 3:

``````Input: l1 = [], l2 = [0]
Output: [0]``````

Constraints:

``````- The number of nodes in both lists is in the range [0, 50].
- -100 <= Node.val <= 100
- Both l1 and l2 are sorted in non-decreasing order.``````

### Explanation

Since the lists are sorted, we can just compare the nodes of the lists and append the smaller node to the new list.

Let's check the algorithm for this approach.

#### Algorithm

``````- return list l2 if list l1 == null

- return list l1 if list l2 == null

- set ListNode *head = null

- if l1->val < l2->val
- move ahead l1 = l1->next
- else
- move ahead l2 = l2->next

- initialize ListNode *p and set p = head

- while(l1 && l2) // l1 and l2 both are not null
- if l1->val < l2->val
- set p->next = l1
- set l1 = l1->next
- else
- set p->next = l2
- set l2 = l2->next

- set p = p->next

// append the pending elements of the remaining list
- if l1 != null
- set p->next = l1
- else
- set p->next = l2``````

#### C++ solution

``````class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if (l1 == NULL){
return l2;
}

if(l2 == NULL) {
return l1;
}

if(l1->val < l2->val){
l1 = l1->next;
} else {
l2 = l2->next;
}

ListNode *p;

while(l1 && l2){
if(l1->val < l2->val){
p->next = l1;
l1 = l1->next;
} else {
p->next = l2;
l2 = l2->next;
}

p = p->next;
}

if(l1 != NULL){
p->next = l1;
} else {
p->next = l2;
}

}
};``````

#### Golang solution

``````func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
if l1 == nil {
return l2
}

if l2 == nil {
return l1
}

if l1.Val < l2.Val {
l1 = l1.Next
} else {
l2 = l2.Next
}

var p *ListNode;

for l1 != nil && l2 != nil {
if l1.Val < l2.Val {
p.Next = l1
l1 = l1.Next
} else {
p.Next = l2
l2 = l2.Next
}

p = p.Next
}

if l1 != nil {
p.Next = l1
} else {
p.Next = l2
}

}``````

#### Javascript solution

``````var mergeTwoLists = function(l1, l2) {
if( !l1 ){
return l2;
}

if( !l2 ){
return l1;
}

let head = new ListNode(0, null);

if( l1.val < l2.val ){
l1 = l1.next;
} else {
l2 = l2.next;
}

while(l1 && l2) {
if (l1.val < l2.val) {
p.next = l1;
l1 = l1.next;
} else {
p.next = l2;
l2 = l2.next;
}

p = p.next;
}

if( l1 ){
p.next = l1;
} else {
p.next = l2;
}

};``````

Let's dry-run our algorithm to see how the solution works.

``````Input: l1 = [1, 2, 4], l2 = [1, 3, 4]

Step 1: if l1 == NULL
false

Step 2: if l2 == NULL
false

Step 3: ListNode *head = NULL;

Step 4: if l1->val < l2->val
1 < 1
false

|
1 -> 3 -> 4

l2 = l2->next

l2
|
1 -> 3 > 4

Step 5: ListNode *p

|
1 -> 3 -> 4

Step 6: loop while l1 && l2
true && true
true

- if l1->val < l2->val
1 < 3
true

p->next = l1

|
1 -> 1

l1 = l1->next

l1
|
1 -> 2 -> 4

p = p->next

|    |
1 -> 1

Step 7: loop while l1 && l2
true && true
true

- if l1->val < l2->val
2 < 3
true

p->next = l1

|    |
1 -> 1 -> 2

l1 = l1->next

l1
|
1 -> 2 -> 4

p = p->next

|         |
1 -> 1 -> 2

Step 8: loop while l1 && l2
true && true
true

- if l1->val < l2->val
4 < 3
false

p->next = l2

|         |
1 -> 1 -> 2 -> 3

l2 = l2->next

l2
|
1 -> 3 -> 4

p = p->next

|              |
1 -> 1 -> 2 -> 3

Step 9: loop while l1 && l2
true && true
true

- if l1->val < l2->val
4 < 4
false

p->next = l2

|              |
1 -> 1 -> 2 -> 3 -> 4

l2 = l2->next

l2
|
1 -> 3 -> 4 -> null

p = p->next

|                   |
1 -> 1 -> 2 -> 3 -> 4

Step 10: loop while l1 && l2
true && false
false

Step 11: if l1 != NULL
true

p->next = l1

|                   |
1 -> 1 -> 2 -> 3 -> 4 -> 4