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.

can you explain how the remaining elements are getting attached??

The runtime is not O(n), but O(N+M), because you have to go through both lists in the worst case.

Can you please explain your code taking an example?

So I basically tried to do the same thing but in C++ but I am getting a segmentation fault error. Any idea why?

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

Note: this solution can be done in-place (i.e directly changing the next pointers of each node, rather than building a new linkedlist with pointers to nodes in A and B)

Node mergeLists(Node headA, Node headB) {
     if(headA == null)
         return headB;
     if(headB == null)
         return headA;
    
     Node head = headA.data < headB.data ? headA : headB;
    
     Node currA = headA, currB = headB;
     while(currA != null && currB != null) {
         if(currA.data < currB.data) {
             Node aNext = currA.next;
             if(aNext == null || aNext.data > currB.data) {
                 currA.next = currB;
             }
             currA = aNext;
         } else {
             Node bNext = currB.next;
             if(bNext == null || bNext.data > currA.data) {
                 currB.next = currA;
             }
             currB = bNext;
         }
     }
    
    return head;
}

I'm confused about the space complexity here. Isn't space complexity O(n+m) as well? You're creating a new linkedlist n which takes the elements of both currA and currB.

This is pretty clean ! Thanks

pretty easy to undarstand, awesome!

Good job. You can get rid of the first if condition though. It seems redundant.

Hi very simple recursive solution to merge two sorted linked list. Recursive algorithm alsays simplifies program a lot. Earlier I was trying to use while loop but it complicated my approach a lot.

You can simplify the first three conditionals into one. "not A or not B" is true when both A and B are None. In that case "headA or headB" assigns None to head.

def MergeLists(headA, headB):
    if not headA or not headB:
        head = headA or headB
        return head

    if headA.data < headB.data:
        smallerNode = headA
        smallerNode.next = MergeLists(headA.next, headB)
    else:
        smallerNode = headB
        smallerNode.next = MergeLists(headA, headB.next)

    return smallerNode

Also - I fear recursion in Python. Here is a non-recursive approach:

def MergeLists(h1, h2):
    if not h1 or not h2:
        return h1 or h2

    head, h1, h2 = (h1, h1.next, h2) if min([h1.data, h2.data]) == h1.data else (h2, h1, h2.next)
    curr = head
    while h1 or h2:

        if not h1 or not h2:
            curr.next = h1 or h2
            return head

        curr.next, h1, h2 = (h1, h1.next, h2) if min([h1.data, h2.data]) == h1.data else (h2, h1, h2.next)
        curr = curr.next
    return head

This is pretty cool. It also works fine if you converted it to JS

@imaginationsuper, THANKS for your solution, but I am still learning Java, and I had a trouble understanding the recursive part (headA.next = MergeLists(headA.next,headB).

Really nice solution and a easy to one to remember.

Agreed. We would'nt need any getters/setters for the Node class, but doing a simple "Node temp = new Node(data)" really comes in handy. I hope the moderators listen :)

do you find the answer on this question?