Leetcode-21 Merge Two Sorted Linked Lists

Leetcode-21 Merge Two Sorted Linked List Difficulty: Easy

This is a linked list related easy problem from leetcode. The problem asks to 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.

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.

Source: Leetcode ^[1]

ALERT, ALERT, ALERT !!!

If you have come to see the solution before trying to solve it yourself, this really won’t help you, promise! If that is the case, we will recommend, please go back and first try it yourself. If you can’t solve it after (at least)an hour of thinking and trying, please come back! 🙂You can solve it here. ^[1]

Solution (Iterative)

Let’s say we have two linked lists l1 and l2 as below. The idea of merging them so that the merged list also remains sorted is to take the minimum value from each pair of the list and append that in a new list.

To create a new list, let’s define a pointer head and assign it to point a newly created dummy node. We will need to return this head finally, so, it should stick to the dummy node. That’s why, to traverse through the new list and append necessary values, we need another pointer. Let’s say we define p as another pointer which will point to the same dummy node as head. So, at this stage, we have the settings as below image.

Now, let’s start comparing both of the first nodes of two lists. (Assume, pointer l1 points to the first list and l2 points to the second one) We see l1->value (10) is greater than or equal to l2->value (5), so, we need to store 5 in a newly created node and append that node in front of p. Since l2‘s value is taken, l2 will move forward to point the next value in the list. The code will look like:

p->next = new ListNode(l2->val); //Here ListNode is the type of node
p = p->next;
l2 = l2->next;

At this stage, l1 is pointing to the same node as before (10) and l2 is pointing to the new node (70). Again, we will compare both values and since l1‘s value is smaller, we will append l1‘s value to p and move forward l1 and p as below.

Now, l1’s value is smaller than l2’s, so, l1’s value will be appended to p; and p and l1 will move forward as below.

Then moves l2.

Now, both l1 and l2 contains equal value. It doesn’t matter which one to move when they are equal. So, we choose l1 to move forward as below.

This way, the algorithm will continue and p will keep appending values in an ascending manner. But how this algorithm will terminate?

We can find that either l1 or l2 will reach to their end (NULL) at some point. Both will not point NULL at the same time. When one will point to NULL, we will simply keep appending the other one’s value to p. When both l1 and l2 will come to their end (both pointing to NULL), then the algorithm will stop. Finally we will return head->next, since it points to the first element (5) of the result list.

Time Complexity

O(n) since we need to traverse both list once

Space Complexity

O(n) since we need to create and additional list to contain the merged list.

Below is the complete code of the algorithm. If you find it hard to understand or any part of the explanation not clear, please leave a comment.

Happy Coding ! 😀

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if(l1 == NULL && l2 == NULL) return NULL;
        if(l1 == NULL && l2 != NULL) return l2;
        if(l1 != NULL && l2 == NULL) return l1;
        
        ListNode* head = new ListNode(0);
        ListNode* p = head;
        
        while(l1 != NULL || l2!= NULL){
            if(l1 == NULL){
                p->next = new ListNode(l2->val);
                p = p->next;
                l2 = l2->next;
            }
            else if(l2 == NULL){
                p->next = new ListNode(l1->val);
                p = p->next;
                l1 = l1->next;
            }
            else{
                if(l1->val <= l2->val){
                    p->next = new ListNode(l1->val);
                    p = p->next; 
                    l1 = l1->next;
                }
                else{
                    p->next = new ListNode(l2->val);
                    p = p->next;
                    l2 = l2->next;
                }
            }
        }
        
        return head->next;
    }
};

[1] Problem Link: Leetcode-21 Merge Two Sorted Linked Lists