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

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

needs higher recursion limit incase of increased size in linked lists.

Its a very late comment, but the solution doesn't pass case 5 and case 6.

Good solution, but it break with for larger test cases because of "Maximum recursion depth exceeded" error:

Here is a less elegant non-recursive one:

def mergeLists(head1, head2):
    if head1 is None:
        return head2
    if head2 is None:
        return head1

    if head1.data <= head2.data:
        head = head1
        curr1 = head1.next
        curr2 = head2
    else:
        head = head2
        curr1 = head1
        curr2 = head2.next

    curr = head
        
    while True:
        if curr1 is None:
            curr.next = curr2
            break
        elif curr2 is None:
            curr.next = curr1
            break

        if curr1.data <= curr2.data:
            curr.next = curr1
            curr1 = curr1.next
        else:
            curr.next = curr2
            curr2 = curr2.next
        
        curr = curr.next

    return head

Tests 5 and 6 are failing with this code

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.

In your github you have this code-

SinglyLinkedListNode result = new SinglyLinkedListNode(0); // dummy/placeholder ListNode SinglyLinkedListNode n = result;

    Why do we write 0 while creating the result object?

Hi Rodney,

Would you mind to explain that why the return 'head' can have result all those data?even though the pointer which you use to travel all elements is 'n'.

@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.

This code show "Runtime error" in the test case 5th and 6th.