Limited Period Offer : 20% Discount on online/offline courses, for more details call/whatsapp

Merge Two Sorted Linked List

1 min read
1 year ago By Aniket Prajapati

Merge two sorted Linked List

Problem Statement .


You are given the heads of two sorted linked lists list1 and list2. Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists. Return the head of the merged linked list.

**Example test Case **

INPUT: list1 = [1,2,4], list2 = [1,3,4] OUTPUT: [1,1,2,3,4,4]

Solution with Dummy Node(Using O(N) Space)

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode* list3;
        ListNode* temp;
        
        if(list1==NULL)
        {
            return list2;
        }
        else if(list2==NULL)
        {
            return list1;
        }
        if(list1->val <= list2->val)
        {
            list3=list1;
            temp=list1;
            list1=list1->next;
            temp->next=NULL;
        }
        else{
            list3=list2;
            temp=list2;
            list2=list2->next;
            temp->next=NULL;
        }
        
        while(list1 !=NULL && list2 !=NULL)
        {
            if(list1->val <= list2->val)
            {
                temp->next=list1;
                temp=temp->next;
                list1=list1->next;
                temp->next=NULL;
            }
            else {
                temp->next=list2;
                temp=temp->next;
                list2=list2->next;
                temp->next=NULL;
            }
        }
        if(list1!=NULL)
        {
            temp->next=list1;
        }
        else{
            temp->next=list2;
        }
        return list3;
    }
};

Optimal Solution :

ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
    
    if(NULL == l1) return l2;
    if(NULL == l2) return l1;
    
    ListNode* head=NULL;    // head of the list to return
    
    // find first element (can use dummy node to put this part inside of the loop)
    if(l1->val < l2->val)       { head = l1; l1 = l1->next; }
    else                        { head = l2; l2 = l2->next; }
    
    ListNode* p = head;     // pointer to form new list
    
    // I use && to remove extra IF from the loop
    while(l1 && l2){
        if(l1->val < l2->val)   { p->next = l1; l1 = l1->next; }
        else                    { p->next = l2; l2 = l2->next; }
        p=p->next;
    }
    
    // add the rest of the tail, done!
    if(l1)  p->next=l1;
    else    p->next=l2;
    
    return head;
}

Reference or to practice the problem link https://leetcode.com/problems/merge-two-sorted-lists/


Aug 12, 2023 03:03 Back to Articles

Other Articles

linked list

A linked list is a linear data structure, in which the elements are not stored at contiguous memory locations. The elements in a linked list are linked using pointers . This elements can be accessed by pointer traversing.

1 year ago By Aniket Prajapati
Web Development as a career !! Web Development as a career !!

Web development offers a fulfilling career designing, developing, and maintaining websites and applications, combining creativity and technical skills in the digital realm.

2 years ago By Mitali Gupta
Quill Editor in laravel livewire

using quill editor in livewire code

1 year ago By Santosh Kshirsagar
Prim's Algorithm

Prim's Algorithm is a graph algorithm and this algorithm works as it starts with a single node and then moves through several adjacent nodes form that node , in order to explore all of the connected edges along the way.

1 year ago By Aniket Prajapati