# Solution For Merge Two Sorted Lists

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:

Create a dummy node and initialize it to NULL.

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

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

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

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

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

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.

## Step by Step Implementation For Merge Two Sorted Lists

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { // create a dummy node to point to the head of the merged list ListNode dummy = new ListNode(); // create a pointer to iterate through the dummy node ListNode current = dummy; // while both l1 and l2 are not null while (l1 != null && l2 != null) { // if the value of l1 is less than or equal to the value of l2 if (l1.val <= l2.val) { // set the next value of current to the value of l1 current.next = l1; // move l1 to the next node l1 = l1.next; } // otherwise else { // set the next value of current to the value of l2 current.next = l2; // move l2 to the next node l2 = l2.next; } // move current to the next node current = current.next; } // if l1 is not null, set the next value of current to the value of l1 if (l1 != null) { current.next = l1; } // if l2 is not null, set the next value of current to the value of l2 if (l2 != null) { current.next = l2; } // return the next value of dummy (which is the head of the merged list) return dummy.next; } }

# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode: # create a dummy head node dummy = ListNode() # set current to the dummy head node current = dummy # while both l1 and l2 nodes exist while l1 and l2: # if l1's value is less than or equal to l2's value if l1.val <= l2.val: # set current's next to l1 current.next = l1 # set l1 to its next l1 = l1.next # otherwise else: # set current's next to l2 current.next = l2 # set l2 to its next l2 = l2.next # set current to its next current = current.next # if l1 exists if l1: # set current's next to l1 current.next = l1 # if l2 exists if l2: # set current's next to l2 current.next = l2 # return the next node after the dummy head node (which is the merged sorted list) return dummy.next

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */ /** * @param {ListNode} l1 * @param {ListNode} l2 * @return {ListNode} */ var mergeTwoLists = function(l1, l2) { //create a new list let list = new ListNode(0); //create a pointer that will be used to iterate through the new list let current = list; //as long as both l1 and l2 are not null while(l1 && l2){ //compare the values of the nodes in l1 and l2 //if the value in l1 is less than the value in l2 //set the current node's next property to the node in l1 //increment l1 if(l1.val < l2.val){ current.next = l1; l1 = l1.next; } //otherwise //set the current node's next property to the node in l2 //increment l2 else{ current.next = l2; l2 = l2.next; } //increment the current node current = current.next; } //set the current node's next property to the remaining list current.next = l1 || l2; //return the merged list return list.next; };

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { // if either list is empty, return the other list if (!l1) return l2; if (!l2) return l1; // create a dummy head for the merged list ListNode* dummyHead = new ListNode(-1); ListNode* mergedList = dummyHead; // traverse both lists, adding the smaller element to the merged list while (l1 && l2) { if (l1->val < l2->val) { mergedList->next = l1; l1 = l1->next; } else { mergedList->next = l2; l2 = l2->next; } mergedList = mergedList->next; } // add any remaining elements from the non-empty list if (l1) mergedList->next = l1; if (l2) mergedList->next = l2; // get rid of the dummy head and return the merged list ListNode* head = dummyHead->next; delete dummyHead; return head; } };

/** * Definition for singly-linked list. * public class ListNode { * public int val; * public ListNode next; * public ListNode(int val=0, ListNode next=null) { * this.val = val; * this.next = next; * } * } */ public class Solution { public ListNode MergeTwoLists(ListNode l1, ListNode l2) { // create a new list to store the merged list ListNode mergedList = new ListNode(); // create two pointers, one for each list ListNode pointer1 = l1; ListNode pointer2 = l2; // while both pointers are not null while(pointer1 != null && pointer2 != null) { // compare the values of the two pointers // if the value of pointer1 is less than or equal to the value of pointer2 if(pointer1.val <= pointer2.val) { // set the next value of the merged list to the value of pointer1 mergedList.next = pointer1.val; // move pointer1 to the next node pointer1 = pointer1.next; // if the value of pointer2 is less than the value of pointer1 } else { // set the next value of the merged list to the value of pointer2 mergedList.next = pointer2.val; // move pointer2 to the next node pointer2 = pointer2.next; } // move mergedList pointer to the next node mergedList = mergedList.next; } // if pointer1 is not null, that means list1 is longer than list2 // so we just need to attach list1 to the end of mergedList if(pointer1 != null) { mergedList.next = pointer1; // if pointer2 is not null, that means list2 is longer than list1 // so we just need to attach list2 to the end of mergedList } else { mergedList.next = pointer2; } // return the merged list return mergedList; } }