Can u explain ur code?

Very nice! Here is C solution using while loop. Not as elegant but easier to understand:

Node* MergeLists(Node *headA, Node* headB)
{
    if (headA == NULL && headB == NULL) {
        return NULL;
    }

    if (headA == NULL) {
        return headB;
    }

    if (headB == NULL) {
        return headA;
    }

    // Ensure that list A starts with the smaller number
    if (headA->data > headB->data) {
        Node *tmp = headB;
        headB = headA;
        headA = tmp;
    }

    Node *listHead = headA;

    while (headB) {
        // Advance through nodes in list A until the next node
        // has data bigger than data at current node of list B
        while (headA->next != NULL &&
               headB->data > headA->next->data) {
            headA = headA->next;
        }

        // Insert current node in list B into list A
        Node* nextB = headB->next;
        headB->next = headA->next;
        headA->next = headB;
        headB = nextB;
    }

    return listHead;
}

If you move the return statement to inside your conditional blocks, you can clean up your headA > headB code by just allowing it to return headB. Here's my solution in Java:

Node MergeLists(Node a, Node b) {
    if (a == null) {
        return b;
    } else if (b == null) {
        return a;
    }

    if (a.data < b.data) {
        a.next = MergeLists(a.next, b);
        return a;
    } else {
        b.next = MergeLists(a, b.next);
        return b;
    }
}

You can also test for one node == null at a time as I did; if either is null it returns the other, and if both are null returning the second node still returns null which is equivalent to what if((headA==NULL)&&(headB==NULL)) does.

Nice solution. For the first three checks, you can simplify to:

if (headA==NULL):
    return headB;
if (headB==NULL):
    return headA;

Because if they are both null, this will just return null which is what we want. But if only one is null, it will return the other.

these 4 lines took me a while to understand Node* tmp= headB; headB = headB->next; temp->next = headA; the original headB now points to headA headA = temp; headA now becomes original headB

It can be written as: Node* tmp = headA; headA = headB; // change the headA to headB headA->next = MergeLists(tmp, headB->next); //tmp is the orginal headA

I hope people can usnstand it better with these 3 lines.

The various solutions in this thread can be further simplified to

    if (headA == null) 
        return headB;

    if (headB != null) {
        if (headA.data < headB.data) {
            headA.next = MergeLists(headA.next, headB);
            return headA;
        } 
        headB.next = MergeLists(headA, headB.next);
        return headB;
    }

    return headA;

My code, which passes all tests:

Node* MergeLists(Node *headA, Node* headB)
{   
    if(!headA)
        return headB;
    if(!headB)
        return headA;
    if(headA->data > headB->data){
        headB->next = MergeLists(headA, headB->next);
        return headB;
    }
    else{
        headA->next = MergeLists(headA->next, headB);
        return headA;
    }
}

Tip: recursion can be by itself confusing, so writing less code, keeps confusion out of the way ;)

why not change the recursive part to this (java code):

if(headA.data<headB.data){
    headA.next = MergeLists(headA.next,headB);
    return headA;
}
else{
    headB.next = MergeLists(headA,headB.next);
    return headB;
}

awesome.. thank you so much

Simpler:

if(!headA){return headB;}
if(!headB){return headA;}
    
if(headA->data < headB->data){
    headA->next = MergeLists(headA->next,headB);
    return headA;
}
else{
    headB->next = MergeLists(headA,headB->next);
    return headB;
}

how else if part of code work ,plss explain.

I get inspiration from your answer：

Node* MergeLists(Node *headA, Node* headB)
{
  // This is a "method-only" submission. 
  // You only need to complete this method 
    if(headA == NULL&& headB != NULL)
        return headB;
    if(headB == NULL&& headA != NULL)
        return headA;
    if(headA == NULL && headB == NULL)
        return NULL;
    if(headA->data < headB->data){
       headA->next = MergeLists(headA->next,headB);
       return headA;
    }
    headB->next = MergeLists(headA,headB->next);
    return headB;
}

Brilliant code!! Can u pls explain why u added headA=temp?? I think the work is completed with temp as soon as u assign temp->next=headA; And can u pls tell me why u r u returning headA for the whole code at the end?? it'd be great if u helped :)

My almost similar code in Java. Did not use Recursion because it will give overflow issue with bigger lists.

Node MergeLists(Node headA, Node headB) {
    Node merged= new Node();
    Node mergedTemp= merged;
    // taking a copy of the head node of new array.
    while(headA !=null || headB !=null)
        {
        // while any of the list has nodes left
        if(headA !=null && headB !=null)
            {
            //while both have elemnts
            if(headA.data<=headB.data)// if list 1 has smaller element add its node to the new list.
                {
                merged.next=headA;
                headA=headA.next;
            }
            else{// else add list 2's element
                merged.next=headB;
                headB=headB.next;
            }
        }
        else if(headA ==null)
            {
            // if list 1 is out of nodes we only add list 2's elements
            merged.next=headB;
            headB=headB.next;
        }
        else if(headB ==null){
            // else if list 2 is out of elements we add list 1's elements;
            merged.next=headA;
            headA=headA.next;
        }
        merged=merged.next;
    }
    return mergedTemp.next;// I started storing elemnts from next location actually thus passing merged.next as head.
}

headA->next = MergeLists(headA->next, headB); can you explain the meaning of this line/

much simplified. same concept but it is easier to just chain with the first parameter and recursively place the smallest head list in that first parameter

Node* MergeLists(Node *headA, Node* headB)
{
     if(!headA&&!headB)
        return NULL;
    if(headA&&!headB)
        return headA;
    if(headB&&!headA)
        return headB;
    
    if(headA->data <= headB->data){
        headA->next = MergeLists(headA->next, headB);
        return headA;
    } else{
        MergeLists(headB,headA);
        return headB;
    }
}

Superb!

Node mergeLists(Node headA, Node headB) { if(headA == null) return headB; else if(headB == null) return headA; Node head = new Node(); if(headA.data < headB.data){ head = headA; head.next = mergeLists(headA.next,headB); }else{ head = headB; head.next = mergeLists(headA,headB.next); } return head; }

Thank you @Dark_Knight19 for giving the solution here only, god bless you bro.

Nice code..!!

We can simplify your solution even furthur. The following is almost the same but appeared easier to understand to me. Actually the else block is simplified.

if((headA==null)&&(headB==null)) return null; if((headA!=null)&&(headB==null)) return headA; if((headA == null)&&(headB!=null)) return headB;

if(headA.data<headB.data){
    headA.next = mergeLists(headA.next, headB);
    return headA;
} else{
     headB.next = mergeLists(headA, headB.next);
    return headB;
}

instead of else if in last section it should be only else.

JAva 7

if (head1 == null && head2 == null) { return null; } if (head1 == null) { return head2; } if (head2 == null) { return head1; } if (head2.data <= head1.data) { SinglyLinkedListNode temp = head2; head2 = head2.next; temp.next = head1; head1 = temp; head1.next = mergeLists(head1.next, head2); } else { head1.next = mergeLists(head1.next, head2); } return head1;

Test Case 5 and 6 showing runtime error in python

U did have to add an greater than equal sign to the else if statement to run the code

else if((headA->data) >= (headB->data))

Thank you Dark_Knight19 for posting your solution! I was struggling with solving this non-recusively for hours, and your post inspired me to try a recursive solution.

I ended up coming up with this solution:

if(head1 == nullptr && head2 == nullptr)
{
    return nullptr;
}
if(head1 == nullptr && head2 != nullptr)
{
    return head2;
}
if(head1 != nullptr && head2 == nullptr)
{
    return head1;
}

if(head1->data < head2->data)
{
    SinglyLinkedListNode * temp = head1->next;
    head1->next = mergeLists(temp, head2);
    return head1;

}
else
{
    SinglyLinkedListNode * temp = head2->next;
    head2->next = mergeLists(temp, head1);
    return head2;
}

C++ simple

SinglyLinkedListNode* head2) {
    if(!head1)
    return head2;
    if(!head2)
    return head1;
else if(head1->data<=head2->data){
    head1->next = mergeLists(head1->next, head2);
    return head1;
    }
else{
    head2->next = mergeLists(head1, head2->next);
    return head2;
}
}

Hi,

In Node* temp = headB,

we are not allocating any memory to temp. therefore if headB value changes to headB.next then temp value has to change to same value as temp and headB are pointing to same address. Can you explain why it is not changing.

static SinglyLinkedListNode mergeLists(SinglyLinkedListNode head1, SinglyLinkedListNode head2) {
    SinglyLinkedListNode l = null;
    SinglyLinkedListNode n1 = head1;
    SinglyLinkedListNode n2 = head2;
    if(n1==null & n2==null) return null;
    if(n1==null) return n2;
    if(n2==null) return n1;
    if(n1.data<=n2.data){
        l = n1;
        l.next = mergeLists(n1.next,n2);
    }else{
        l = n2;
        l.next = mergeLists(n1,n2.next);
    }

return l;
}

this is simpler

SinglyLinkedListNode* mergeLists(SinglyLinkedListNode* head1, SinglyLinkedListNode* head2) { if(head1==NULL && head2==NULL) { return head1; } else if(head1==NULL) { return head2; } else if(head2==NULL) { return head1; } else { if (head1->datadata) { head1->next=mergeLists( head1->next,head2 ); return head1;

} else { head2->next=mergeLists(head1,head2->next); return head2; }

} }**

much shorter version:

// handle end of list
if(head1 == NULL){
    return head2;
}
if(head2 == NULL){
    return head1;
}

// handle sorting
if(head1->data < head2->data){
    head1->next = mergeLists(head1->next, head2);
    return head1;
}
head2->next = mergeLists(head1, head2->next);
return head2;

python3

def mergeLists(head1, head2):
    temp=[]
    cur=head1
    while cur:
        temp.append(cur.data)
        cur=cur.next
    cur=head2
    while cur:
        temp.append(cur.data)
        cur=cur.next
    temp.sort()
    llist=SinglyLinkedList()
    for i in temp:
        llist.insert_node(i)
    return llist.head

why headA = temp ? i don't understand this part

It exceeds the recursion depth

Would these two work in place of the first 3 if-statement above?

if ((headA==NULL) return headB; if ((headB==NULL) return headA;

The idea is that even if both are NULL, it will just return the other which is NULL.

Am I missing something in my though ?

nice

This is so much better than the code given in editorial.

This solution does not need extra space to store the Node. (Although it does have a temp Node pointer, but node pointer is fine, storing the object Node would be big space consuming and interviewer will definitely ask to improve upon the solution given in the editorial)

Btw, you can also avoid to have that extra temp node pointer in the else condition.

An iterative solution in Python

def mergeLists(head1, head2):
    merged_list = SinglyLinkedList()
    while(head1 is not None and head2 is not None):
        if head1.data < head2.data:
            merged_list.insert_node(head1.data)
            head1 = head1.next
        elif head1.data > head2.data:
            merged_list.insert_node(head2.data)
            head2 = head2.next
        else:
            merged_list.insert_node(head1.data)
            merged_list.insert_node(head2.data)
            head1 = head1.next
            head2 = head2.next
    while(head1 is not None):
        merged_list.insert_node(head1.data)
        head1 = head1.next
    while(head2 is not None):
        merged_list.insert_node(head2.data)
        head2 = head2.next
    return merged_list.head

Interesting. Is that in C or is it pseudocode?

here is simple code in java...

static SinglyLinkedListNode mergeLists(SinglyLinkedListNode head1, SinglyLinkedListNode head2) {   
        if(head1==null){return head2;}
        if(head2==null){return head1;}
        
        SinglyLinkedListNode head3 = null;
        if(head1.data<head2.data){
            head3 = head1;
            head1=head1.next;
        }else{
            head3 = head2;
            head2 = head2.next;
        }
        SinglyLinkedListNode temp = head3;
        while(head1!=null&&head2!=null){
            if(head1.data<head2.data){
                temp.next = head1;
                head1 = head1.next;
            }else{
                temp.next = head2;
                head2 = head2.next;
            }
            temp = temp.next;
        }
        if(head1==null){
            temp.next = head2;
        }else{
            temp.next = head1;
        }
        return head3;
        
    }

instead of writing three condition for checking null like this:

if((headA==NULL)&&(headB==NULL) return NULL; if((headA!=NULL)&&(headB==NULL)) return headA; if((headA == NULL)&&(headB!=NULL)) return headB;

you can write:

if(head1==nullptr) return head2;

if(head2==nullptr) return head1;

Here is another solution with recursive {

    if (!head1 && !head2)
    return nullptr;
else if (!head1 || !head2)
    return head2 ? head2 : head1;

SinglyLinkedListNode* merged;
SinglyLinkedListNode* temp;

if (head1->data <= head2->data)
{
    merged = head1;
    temp = head2;
}
else
{
    merged = head2;
    temp = head1;
}

merged->next = mergeLists(merged->next, temp);

return merged;

}

super