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

React State Management Made Easy: Zustand and Redux Explained React State Management Made Easy: Zustand and Redux Explained

In this article, we will discover two powerful state management libraries for React: Zustand and Redux. Also explore their unique approaches, advantages, and use cases, to simplify and optimize your application's state handling. Choose the best fit for your project's needs and boost development efficiency with these popular solutions.

1 year ago By Mitali Gupta
Livewire contenteditable to variable using entagle

using livewire apline js to update variable in livewire component

1 year ago By Santosh Kshirsagar
Binary Search top interview questrions.

As we know binary search itself is a imp topic to be learned in Data Structures and Algorithm so, This article contains all the important questions that can be asked in coding interview or online assessment(OA) . Here the questions clear all the concepts and the variety in questions helps to understands the logic behind the concepts .

1 year ago By Aniket Prajapati
Best Websites for Building Resumes

In this article, we will explore five top websites that can assist you in crafting a compelling resume to increase your chances of getting shortlisted by companies.

1 year ago By Mitali Gupta