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

Introduction to Django

A high-level Python web framework called Django makes it possible for programmers to create web applications rapidly and effectively. It adheres to the Model-View-Controller (MVC) architectural design pattern, placing emphasis on the division of duties and encouraging code reuse. Django offers a comprehensive collection of conventions, frameworks, and tools that speed up development and promote best practises.

Mastering the Fundamentals: Basic HTML Tags for Web Development Mastering the Fundamentals: Basic HTML Tags for Web Development

In this article, we'll explore the Basic HTML elements that form the foundation of every web page.

2 years ago By Mitali Gupta
Establishing Validation by Converting TypeScript Code to Zod Schemas Establishing Validation by Converting TypeScript Code to Zod Schemas

In this article, we'll explore how to establish validation by converting TypeScript code to Zod schemas. Zod is a TypeScript-first schema validation library that ensures data validity at runtime.

2 years ago By Mitali Gupta
Things you should learn to become good web developer for any tech stack

In this articles all concepts covered to become web developer

1 year ago By Santosh Kshirsagar