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