# 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](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.

```
- return list l2 if list l1 == null  
  
- return list l1 if list l2 == null  
  
- set ListNode *head = null  
  
- if l1->val < l2->val  
  - set head = l1  
  - move ahead l1 = l1->next  
- else  
  - set head = l2  
  - 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;  
        }  
  
        ListNode *head = NULL;  
  
        if(l1->val < l2->val){  
            head = l1;  
            l1 = l1->next;  
        } else {  
            head = l2;  
            l2 = l2->next;  
        }  
  
        ListNode *p;  
        p = head;  
  
        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;  
        }  
  
        return head;  
    }  
};
```

**Golang solution**

```
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {  
    if l1 == nil {  
        return l2  
    }  
  
    if l2 == nil {  
        return l1  
    }  
  
    var head *ListNode  
  
    if l1.Val < l2.Val {  
        head = l1  
        l1 = l1.Next  
    } else {  
        head = l2  
        l2 = l2.Next  
    }  
  
    var p *ListNode;  
    p = head;  
  
    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  
    }  
  
    return head  
}
```

**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 ){  
        head = l1;  
        l1 = l1.next;  
    } else {  
        head = l2;  
        l2 = l2.next;  
    }  
  
    let p = head;  
  
    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;  
    }  
  
    return head;  
};
```

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  
  
        head = l2  
  
        head  
          |  
          1 -> 3 -> 4  
  
        l2 = l2->next  
  
               l2  
               |  
          1 -> 3 > 4  
  
Step 5: ListNode *p  
        p = head  
  
  
        head, p  
          |  
          1 -> 3 -> 4  
  
Step 6: loop while l1 && l2  
        true && true  
        true  
  
        - if l1->val < l2->val  
          1 < 3  
          true  
  
          p->next = l1  
  
          head, p  
           |  
           1 -> 1  
  
          l1 = l1->next  
  
               l1  
               |  
          1 -> 2 -> 4  
  
          p = p->next  
  
          head  p  
           |    |  
           1 -> 1  
  
Step 7: loop while l1 && l2  
        true && true  
        true  
  
        - if l1->val < l2->val  
          2 < 3  
          true  
  
          p->next = l1  
  
          head  p  
           |    |  
           1 -> 1 -> 2  
  
          l1 = l1->next  
  
                   l1  
                    |  
          1 -> 2 -> 4  
  
          p = p->next  
  
          head       p  
           |         |  
           1 -> 1 -> 2  
  
Step 8: loop while l1 && l2  
        true && true  
        true  
  
        - if l1->val < l2->val  
          4 < 3  
          false  
  
          p->next = l2  
  
          head       p  
           |         |  
           1 -> 1 -> 2 -> 3  
  
          l2 = l2->next  
  
                   l2  
                    |  
          1 -> 3 -> 4  
  
          p = p->next  
  
          head            p  
           |              |  
           1 -> 1 -> 2 -> 3  
  
Step 9: loop while l1 && l2  
        true && true  
        true  
  
        - if l1->val < l2->val  
          4 < 4  
          false  
  
          p->next = l2  
  
          head            p  
           |              |  
           1 -> 1 -> 2 -> 3 -> 4  
  
           l2 = l2->next  
  
                         l2  
                          |  
          1 -> 3 -> 4 -> null  
  
          p = p->next  
  
          head                 p  
           |                   |  
           1 -> 1 -> 2 -> 3 -> 4  
  
Step 10: loop while l1 && l2  
         true && false  
         false  
  
Step 11: if l1 != NULL  
         true  
  
         p->next = l1  
  
         head                 p  
          |                   |  
          1 -> 1 -> 2 -> 3 -> 4 -> 4  
  
Step 12: return head;  
  
         head  
          |  
          1 -> 1 -> 2 -> 3 -> 4 -> 4
```