Merge Two Sorted Lists - Leetcode Solution

Problem statement:

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

Example:

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

Solution:

The problem requires us to merge two sorted linked lists into a new sorted list. We will take an iterative approach and maintain a dummy linked list to store the merged list.

We will do the following steps:

1. Create a dummy node and initialize it to NULL.

2. Create a pointer ‘tail’ and initialize it to NULL.

3. Traverse the linked lists being merged. While either of the lists still has nodes, we compare the head nodes of both the lists.

4. We find the node with the smallest value and add it to our dummy list.

5. We then remove the node from the list we picked it from and move the tail pointer to point to the added node.

6. We then update the head pointer of that list and repeat steps 3-5 until both lists are empty.

7. Finally, we return the pointer to the dummy node.

Code:

/**

• 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) {

   ListNode* dummy = new ListNode(-1);
   ListNode* tail = dummy;
   
   while(l1 != NULL && l2 != NULL){
       if(l1->val <= l2->val){
           tail->next = l1;
           l1 = l1->next;
       } else {
           tail->next = l2;
           l2 = l2->next;
       }
       tail = tail->next;
   }
   
   if(l1 != NULL) tail->next = l1;
   if(l2 != NULL) tail->next = l2;
   
   return dummy->next;
  

  } };

Time Complexity: O(n), where n is the total number of nodes in the two lists.

Space Complexity: O(1), as we are not using any extra space.

1