Alkesh

LeetCode - Merge Two Sorted Lists

Container

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
  - 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;
};

Dry Run

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
Share this post!