# Merge two sorted linked lists

# Merge two sorted linked lists

Dark_Knight19 + 31 comments Here is a simple recursive solution that passes both test cases!

`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); else if(headA->data > headB->data) { Node* temp = headB; headB = headB->next; temp->next = headA; headA = temp; headA->next = MergeLists(headA->next, headB); } return headA;`

}

Archish + 1 comment Can u explain ur code?

Dark_Knight19 + 3 comments yea .... i start comparing elements of both linked lists A and B(say) one by one from beginning and my final solution will be the linked list A . so here's how it works :- if the element of A is less than B then i simply move the pointer by one position in forward direction and if the element in list B is less then i need to incorporate that element in A and for that i use temp pointer and this time i move pointer of b forward by one since i have parsed it's element. And finally when i have parsed all elements of one list then i know i no longer need to compare and simply join the other remaining list to my solution (the first three ifs take care of this case).

etayluz + 2 comments I think you're not addressing the case where:

headA->data == headB->data

I would make this change in the forth if statement:

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

Dark_Knight19 + 2 comments Umm yeah i think i forgot that .... thanks for pointing it out :)

wemiao + 3 comments Thanks for sharing your solution Dark _ Knight19! I had figured out the "base case," but I was struggling with finishing the recursive part. I rewrote your code based on etayluz' comment and also slightly more efficient (it's less understandable than your code but less checks based on prior logic).

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

arik_raysar + 1 comment I think that the nested 'else if' wont be a much help in this case as the condition needs to be checked for all three 'if's in a case where A & B are not null. In case one of them is null it gets terminated without checking the remaining 'if's as it just simply returns a value. so I found no great optimization with nested 'else if' with this solution. Correct me if I am wrong. Happy coding.

luca_guarro + 0 comments You are right. We can just have:

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

pvamsi4b3 + 5 comments for those who need it in java, here it is!

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

vmsaigiridhar + 1 comment Nice one. I did it this way Node mergeLists(Node headA, Node headB) { if (headA == null && headB == null) return null; else if (headA == null) return headB; else if (headB == null) return headA; if(headA.data <= headB.data){ headA.next = mergeLists(headA.next, headB); return headA; } else { headA.next = mergeLists(headA, headB.next); return headB; } }

nikhita + 0 comments did it work?

jatinkr30 + 0 comments Thanks

hooni + 0 comments nice solution.

The latter part of the code can be slightly shortened:

if(headA.data >= headB.data) { Node temp = headB; headB = headB.next; temp.next = headA; headA = temp; } headA.next = mergeLists(headA.next,headB); return headA;

taurus05 + 0 comments Code post mat kar hero. bakiyo ko bhi karne de thodi mehnat.

rkm350 + 0 comments @pvamsii43 what is the difference if you write the last else condition as given below?

`Node temp = headB; temp.next = headA; headA = temp; headB = headB.next; headA.next = mergeLists(headA.next, headB);`

I tried this code and it gave a non terminating output.

Aman_yadav_min17 + 0 comments SinglyLinkedListNode* mergeLists(SinglyLinkedListNode* head1, SinglyLinkedListNode* head2) { if(head1==NULL && head2==NULL){ return NULL; } if(head1==NULL && head2!=NULL){ return head2; } if(head1!=NULL && head2==NULL){ return head1; } if(head1->data<=head2->data){ head1->next=mergeLists(head1->next,head2); } else{ head2->next=mergeLists(head1,head2->next);

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

h961853266 + 0 comments SinglyLinkedListNode* mergeLists(SinglyLinkedListNode* head1, SinglyLinkedListNode* head2) {

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

} well..I think my code is easier to understand

nikhilausta + 2 comments please send de solution

vishal546 + 1 comment if (headA == NULL && headB == NULL) return NULL; else if (headA == NULL) return headB; else if (headB == NULL) return headA;

if(headA->data <= headB->data) headA->next = MergeLists(headA->next, headB);

else { Node* temp = headB; headB = headB->next; temp->next = headA; headA = temp; headA->next = MergeLists(headA->next, headB); }

return headA;

pandeyanand9023 + 0 comments Can you please explain the else part

tricerabottoms + 1 comment No problem! I give you best solution. In python the third.

p = 0 def mergeLists(head1, head2): global p r, q, p = 0, p, sys.stdin.tell() sys.stdin.seek(q) a = sys.stdin.read(p-q).split() print(a) q or a.pop(r) while r < len(a): r += int(a.pop(r)) a.sort(key=lambda v: (len(v), v)) fptr.write(' '.join(map(str, a)))

nirajkamdar27 + 1 comment please explain your code

tricerabottoms + 0 comments It very simple. The mergeLists function is called many times. Each time the input in sys.stdin more than last time. So we have to find out where we are and where we're going. That is q and p. Once we know that, we can get only the new stuff.

The new stuff we store in a. But there are traps! The very first data is nonsense, so we pop it off. Then the next data is also a trap, but it is a number that tells us where the next trap is. Those traps are all in the same way, so we pop them all off in a while loop.

All we have left is pure data. But the data has to be in the right order to make the checkmarks green. So we sort the data. First we sort by the length of the data, because the longer the data is, the more valuable it is. Then we sort by the content of data, which sometimes makes it more valuable too, but not as much as the length.

When the data is nice and ordered, we can put it all together and write it up on the fptr. That is how the data escapes the program and makes you winner.

thongcak + 1 comment Hi D_K, I just wonder if your code will compare the remaining of class A in case B is all null already, but A is still unsorted ? because I see you only compare A and B, and when B is null, such as when A has 10 elements and B has only 1 element, program just stop after pushing that one element of B into minimal position in A without going further and sort A.

It is correct in case A is already sorted tho.

phoenixRises + 0 comments The question says A and B are already sorted.

zelataino + 1 comment Can someone explain to me how the previous node in A points to the new value of A after it has passed. Let me explain:

A: 1->3->NULL

....^

B: 2->4->6->NULL

....^

Initially we start at the head of the lists. Since 1 < 2 it becomes

A: 1->3->NULL

..........^

B: 2->4->6->NULL

....^

Now, I understand that 2 points to 3 and 4 becomes the new head after that block of code, but when does 1 point to 2 since the pointer has already passed it? To me, it looks like 1 and 2 are pointing to 3.

chaudharyneha261 + 0 comments SinglyLinkedListNode* mergeLists(SinglyLinkedListNode* p, SinglyLinkedListNode* q) { SinglyLinkedListNode* sm, *startm; if(p->data<=q->data) { startm=p; p=p->next; } else { startm=q; q=q->next; } sm=startm; while(p!=NULL&&q!=NULL) { if(p->data<=q->data) { sm->next=p; sm=sm->next; p=p->next; } else { sm->next=q; sm=sm->next; q=q->next; } } if(p==NULL) sm->next=q; else sm->next=p; return startm; }

etayluz + 3 comments 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; }`

costashsrc + 1 comment First check (headA == NULL && headB == NULL) is not necessary because the following two will handle it.

agodfrey3 + 1 comment No, you need this. The first one handles if they are both NULL. The second handles if only one is NULL. If we ask about if one is NULL, without knowing about the second, we would need yet another if statement inside of it.

askarovdaulet + 0 comments I disagree. If both are NULL, then

if (headA == NULL) return headB;

will trigger and return NULL since that is what headB equals to. And we did expect NULL, so the case of two NULLs is indeed redundant.

e_leftis + 0 comments I believe you can set nextB = headA->next at once and skip the extra step of changing the pointer with headB->next.

himanshusharmah1 + 0 comments Thank you for this,it is realy helpful,and apart from that if you can give me some resources to understand recursion cause I am not getting it in an effective manner. thanks.

Ailuridaes + 9 comments 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.

ak47gyani + 0 comments Nicely done!!

swojit + 2 comments if (headA == null || headB == null) { return (headA == null) ? headB: headA; } if (headA.data < headB.data) { headA.next = MergeLists(headA.next, headB); return headA; } headB.next = MergeLists(headB.next, headA); return headB;

Do you think this is a bit simpler? I know it tests twice.

PS: How to attach code?

phoenixRises + 2 comments You need to press enter twice followed by a tab:

`public static void main(String [] args)`

And then enter for a new line in the code. The text appears brown when it's formatted as code.

prashanthnani + 0 comments [deleted]EmberQuill + 0 comments If you want syntax highlighting, you can use the following syntax:

````java (code) ````

Replace "java" with the language of your choice. python3, ruby, c++, etc.

mugeesh + 0 comments didn't work

ibarry + 1 comment Can you please explain your code?

nikhita + 0 comments consider head1: 4 ->5 ->6 and head2: 1 ->2 ->10 i am sure you might have understood if head1 is null then return head2, and vice versa now with.

if(head1.data>=head2.data) { head2.next=mergeList(head1,head2.next); return head2; }

- this part of code essentially means, the next element to head 1(element 4) would be the result of the comparison between 4 and next head2's element which is 2.
- now the result of the comparison between 4 and 2 would be assigned next to 4.
so, if head1's element is the largest, that ll be the final result of final comparison in this part of the code. but it would fail in the case, where 4(head1) is compared to 10(head2), where it goes to the else part.

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

here head1's next element,i.e 5 is compared to current head2 i.e 10, again first part of code(comparison if clause) is executed, where it again fails coz 10>5. then 10 is compared to 6, and again 10>6. so head1 is returned, which is 6,with the head2 s elemnt i.e 10. and if you observe closely , this comparison was assigned to head1(6)'s next.

now this 10 will bubble up to the previous part where it becomes 6->10. now this link moves up and becomes 5->6->10, which moves up to be 4->5->6->10, again 2->4->5->6->10 and finally becomes 1->2->4->5->6->10.

hope it helped understand recursion.

pulekar_aditya + 0 comments Sweet..nice solution!

peta_vinay + 0 comments wow so simple to understand

piyushmishra + 0 comments amazing

ElizaW + 0 comments This is pretty!

nish456 + 0 comments What's the time complexity of your solution?

abhilashbaddam + 0 comments I like this solution. What is the time complexity over in this solution.

lose311 + 0 comments 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.

hungjen + 0 comments 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.

lzutao + 0 comments [deleted]tschul + 0 comments 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;

shanavas + 0 comments [deleted]whoiscris + 2 comments 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 ;)positivedeist_07 + 0 comments Hey @whoiscris can u pls explain how does the code work?? I'm stuck by the recursion part here :( i don't get it right

GHarshita + 0 comments Can you please explain your code by taking an example?? I am new to recursion.

kamaldheeraj + 0 comments 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; }`

Adit_Shah + 0 comments awesome.. thank you so much

thomas_doutre + 1 comment 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; }

moshahmed + 0 comments Simpler

Node* MergeLists(Node *a, Node*b) { if( !a) return b; if( !b) return a; if (a->data < b->data) { a->next = MergeLists(a->next, b); return a; } else { return MergeLists(b, a); } }

Sentinal_prime + 0 comments how else if part of code work ,plss explain.

blackL + 0 comments 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; }

positivedeist_07 + 0 comments 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 :)

ujjwalsaxena + 4 comments 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. }

Prashantkr314 + 1 comment Essentially the same thing but little clean and easy to understand

/* class Node { int data; Node next; } */ Node mergeLists(Node headA, Node headB) { Node a = headA; Node b = headB; Node c = null; if(a == null || b == null) // either of them is null return a == null? b:a; // getting the first index pointed by c, done this so now in the coming loop i can use next directly on c if(a.data < b.data ){ c = a; a = a.next; }else{ c = b; b = b.next; } Node head = c; // either one of a or b has been changed, while(a != null && b != null){ // ie going to the last elements of the linked lists if(a.data < b.data ){ c.next = a; a = a.next; }else{ c.next = b; b = b.next; } c = c.next; } // either one of a and b is finished // a is left if(a != null) c.next = a; // b is left if(b != null) c.next = b; return head; }

keshavgaur111 + 0 comments Thanks for this nice and easy to understand solution.

prachidwivedi + 0 comments why you wrote it as merged.next instead of merged simply.

prachidwivedi + 0 comments why you wrote it as merged.next

mugeesh + 1 comment Node mergeLists(Node headA, Node headB) { Node head= new Node(); Node headTemp= head; while(headA !=null || headB !=null) { if(headA.data<=headB.data && headA !=null && headB !=null) { head.next=headA; headA=headA.next; } else if(headA.data>=headB.data &&headA !=null && headB !=null){ head.next=headB; headB=headB.next; } else if(headA ==null){ head.next=headB; headB=headB.next; } else if(headB ==null){ head.next=headA; headA=headA.next; } head=head.next; } return headTemp.next; }

mugeesh + 0 comments Why this is not working , can anybody give me the explaination please

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

pooleapply + 0 comments 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; } }

alpha52omega41 + 0 comments Superb!

ak3933 + 0 comments 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; }

Samurai_Jack_ + 0 comments Thank you @Dark_Knight19 for giving the solution here only, god bless you bro.

vikasbaghel26 + 0 comments Nice code..!!

psyentist + 0 comments [deleted]Vivic + 0 comments 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; }`

phoenixking25 + 0 comments instead of else if in last section it should be only else.

mikelee89 + 0 comments 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;

nitinverma1394 + 1 comment Test Case 5 and 6 showing runtime error in python

schiebermc + 0 comments You are hitting python's default recursion limit (which is quite conservative). Either revert your implementation into loops or use

`sys.setrecursionlimit()`

to increase the recursion depth.

sroy02988 + 0 comments 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))**cricha50 + 0 comments 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; }`

uservks + 0 comments ### 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; } }

sumanthk + 0 comments 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.

calvin_k_stone + 8 comments Heres the recursive python 2 / 3 solution I came to.

def MergeLists(headA, headB): if headA is None and headB is None: return None if headA is None: return headB if headB is None: return headA if headA.data < headB.data: smallerNode = headA smallerNode.next = MergeLists(headA.next, headB) else: smallerNode = headB smallerNode.next = MergeLists(headA, headB.next) return smallerNode

maximshen + 0 comments This is pretty clean ! Thanks

omike1900 + 0 comments pretty easy to undarstand, awesome!

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

omar_s_mustafa + 0 comments [deleted]arunkumar_123 + 0 comments 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.

DanHaggard + 3 comments 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

abidkhan484 + 0 comments [deleted]abidkhan484 + 0 comments can you please explain how this line (1) handle min function when h1 is None. what is the output of line2

i am confused...

`head, h1, h2 = (h1, h1.next, h2) if min([h1.data, h2.data]) == h1.data else (h2, h1, h2.next) min(None, 3)`

thedurphy + 1 comment @DanHaggard If you use the

`key`

argument in`min`

/`max`

, you can clean the code up quite a bit. Recursive example.def MergeLists(headA, headB): if not headA or not headB: head = headA or headB return head head = min([headA, headB], key = lambda x:x.data) head.next = MergeLists(head.next, max([headA, headB], key = lambda x:x.data)) return head

GeoMatt22 + 1 comment The cleanest way to do this would be to define

`Node`

ordering using`data`

.For example, this works:

def lt(self, other): return self.data < other.data Node.__lt__ = lt def MergeLists(A, B): if not A or not B: C = A or B else: C = min([A, B]) C.next = MergeLists(C.next, max([A, B])) return C

eloyekunle + 0 comments This is really good!

ebram_tharwat + 0 comments This is pretty cool. It also works fine if you converted it to JS

ganesancit + 0 comments needs higher recursion limit incase of increased size in linked lists.

RodneyShag + 9 comments ### O(1) space complexity Java solution

From my HackerRank solutions.

Runtime: O(n +m)

Space Complexity: O(1)Any recursive solution will take at least O(n+m) space due to O(n+m) recursive calls. Try to do it iteratively for a more space efficient solution.

Node MergeLists(Node currA, Node currB) { if (currA == null) { return currB; } else if (currB == null) { return currA; } /* Find new head pointer */ Node head = null; if (currA.data < currB.data) { head = currA; currA = currA.next; } else { head = currB; currB = currB.next; } /* Build rest of list */ Node n = head; while (currA != null && currB != null) { if (currA.data < currB.data) { n.next = currA; currA = currA.next; } else { n.next = currB; currB = currB.next; } n = n.next; } /* Attach the remaining elements */ if (currA == null) { n.next = currB; } else { n.next = currA; } return head; }

### Let's try an example

List A: 1 -> 4 -> null List B: 2 -> null Created: null

Now the code labeled

**Find new head pointer**will give us the following result:List A: 4 -> null List B: 2 -> null Created: 1 -> null

The code labeled

**Build rest of list**will then give us:List A: 4 -> null List B: null Creaetd: 1 -> 2

Finally, the code labeled

**Attach the remaining elements**will complete our list:List A: null List B: null Created: 1 -> 2 -> 4

Let me know if you have any questions.

anujs23596 + 2 comments can you explain how the remaining elements are getting attached??

RodneyShag + 0 comments When we reach the part of the code that says "Attach the remaining elements", we have already attached all the elements from 1 list, and only some (if any) of the elements from the other list. For whichever original list that still has elements in it, we simply attach them to the end of the list we've been making. This is done in 1 step, by having the tail element in our new list point to the head element of whichever list still has elements in it.

RodneyShag + 0 comments When we reach the part of the code that says "Attach the remaining elements", we have already attached all the elements from 1 list, and only some (if any) of the elements from the other list. For whichever original list that still has elements in it, we simply attach them to the end of the list we've been making. This is done in 1 step, by having the tail element in our new list point to the head element of whichever list still has elements in it.

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

RodneyShag + 0 comments I agree. Fixed. Thanks.

JordanT + 1 comment But taking X := MAX(N,M) means we can say O(2X) -> O(X) == O(N) Therefore it is O(N).

Right?

RodneyShag + 1 comment if you want X := MAX(N,M) then you can say it's O(2X) -> O(X). But you cannot then say it's O(X) -> O(N) since X depends on M

JordanT + 1 comment I was ambiguous in that, I apologize. Let me rephrase below.

O(N+M), as we are checking for worse case, lets make N = the larger of N,M. Therefore O(N+M) -> O(N+N) == O(2N) == O(N).

RodneyShag + 1 comment Yes, in your runtime analysis, if you set N = the larger of N, M, then your runtime is O(N).

JordanT + 1 comment So you were correct in your original analysis. The correction from O(N) to O(N+M) is wrong.

RodneyShag + 1 comment Well my original analysis

**did not indicate that I was setting N as the larger of N and M**, so in that case it's O(N+M).If I indicated N is larger of N and M, then I could have said runtime is O(N).

Either way is fine. My runtime in my post above is consistent.

JordanT + 0 comments Big-oh by definition is bounding the worst case. The worst case is when they are both the same length, i.e. when N and M are both equal to N.

You get O(2N) in that case. i.e. O(N).

All im saying is rudaliszkas' "correction" is wrong, in the sense that it is saying exactly what you had originally, only your original answer is how it is always expressed in big-oh.

GHarshita + 1 comment Can you please explain your code taking an example?

RodneyShag + 1 comment Hi. I added an example for you to my original post above. Hope it helps.

bhuvnesh_kumar + 1 comment Can you please add github repo for javascript as well as i am javascript developer.Also would you help me how would i become good in data structures and algorithm. I am good in langauges and pickup any technology but not upto satsiying level in data structure.

RodneyShag + 1 comment I'm horrible in Javascript - Re-solving 300 problems in Javascript to create a repo sounds like a nightmare.

For Data Structures and Algorithms, you can do the Easy/Medium problems in the corresponding tracks on HackerRank. You can also buy "Cracking the Coding Interview", which is how I mastered the topic (and coincidentally, was working on problems from the book today!

bhuvnesh_kumar + 1 comment Its okay not to create github repo again .I can undersatnd, i just casuelly asked.I already started practicing data strctures in hackerank regularly.will 3-4 months regular practice woulbe help me to reach at satisying level? or in state where i would be able to crack interviews of Amazon, Microsoft kind of tier-1 organization since they majorly focus on DS and Algo. I searched and found there are many books with tiltle "Cracking the Coding Interview". Could you please mention writer name?. I would purchage.

Anyways thanks a lot for your immediate response.

RodneyShag + 0 comments Yes, I recommend solving 50-100 problems on HackerRank, for problems of easy/medium difficulty, and then mastering "Cracking the Coding Interview" by Gayle McDowell

luca_guarro + 2 comments 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; }

RodneyShag + 1 comment luca_guarro + 0 comments wow okay thanks :)

akshitagarwal11 + 0 comments Thank You bro you helped me A lot

kewltek + 0 comments [deleted]sicter + 0 comments 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; }

dozer + 1 comment 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.

RodneyShag + 0 comments In the function, we only create 2 Node variables. We don't create any arrays of size n or m.

While creating the linked list, we just change where the pointers point. We don't copy/duplicate any data.

dozer + 0 comments [deleted]palashrawat7 + 1 comment 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?`

RodneyShag + 1 comment We end up returning

`result.next`

, so, it doesn't matter what value we store in this "dummy" node. You can store any value here.palashrawat7 + 1 comment result.next is returning the head right?

RodneyShag + 1 comment Yes, it's returning the "new" head (basically getting rid of the dummy).

palashrawat7 + 1 comment So if currA is :- 1->2->2->4 and currB is:- 3->->5->6

The result would be (n= 1->2->2->3->4->5->6)

So "return result.next" would return what?

Why we are not returning the "n" as it is the new merged linked list of "currA" and "currB"?

RodneyShag + 0 comments result would be

`0 - 1 - 2 - 2 - 3 - 4 - 5 - 6`

result.next would be

`1 - 2 - 2 - 3 - 4 - 5 - 6`

imaginationsuper + 2 comments Node MergeLists(Node headA, Node headB) { // This is a "method-only" submission. // You only need to complete this method if (headA == null) return headB; else if (headB == null) return headA; else if (headA.data <= headB.data){ headA.next = MergeLists(headA.next, headB); return headA; } else { headB.next = MergeLists(headA, headB.next); return headB; } }

harrisonthu + 1 comment @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).

imaginationsuper + 0 comments Since headA.data is smaller than headB.data, it select out headA and link headA.next from the rest of A list and whole B list. Hope this helps.

atuncatunc + 0 comments Really nice solution and a easy to one to remember.

vivek_23 + 1 comment Please provide constructor structure for Node class from now on. I coded this problem assuming there would be a parameterized constructor but it happened to be a default constructor :|

[deleted] + 1 comment 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 :)

rashedulrubel + 0 comments [deleted]

possen + 1 comment This is a fairly compact and efficent non-recursive solution.

`def MergeLists(nodeA, nodeB): mergedHead = Node() # dummy node so can be handled the same merged = mergedHead while nodeA != None or nodeB != None: if nodeA == None: merged.next = nodeB break elif nodeB == None: merged.next = nodeA break else: if nodeA.data < nodeB.data: merged.next = nodeA nodeA = nodeA.next else: merged.next = nodeB nodeB = nodeB.next merged = merged.next return mergedHead.next`

smarsh + 0 comments Best solution in the entire thread! Great job.

vedvasa + 0 comments Simple Python3 solution: Easy to Understand recursive approach

def MergeLists(headA, headB): if(headA is None): return headB elif(headB is None): return headA if(headA.data <= headB.data): result = headA result.next = MergeLists(headA.next, headB) else: result = headB result.next = MergeLists(headA, headB.next) return result

parasmyname + 0 comments Solution without recursion

static SinglyLinkedListNode mergeLists(SinglyLinkedListNode head1, SinglyLinkedListNode head2) { if(head1==null) return head2; else if(head2==null) return head1; else if(head1==null && head2==null) return null; else{ SinglyLinkedListNode dummynode=new SinglyLinkedListNode(0); SinglyLinkedListNode tail=dummynode; //1->5->6->9->11 //1->3->4->8-9->10->11->100 SinglyLinkedListNode node1=head1; SinglyLinkedListNode node2=head2; while(node1!=null && node2!=null){ if(node1.data<=node2.data){ SinglyLinkedListNode temp=new SinglyLinkedListNode(node1.data); tail.next=temp; node1=node1.next; } else{ SinglyLinkedListNode temp=new SinglyLinkedListNode(node2.data); tail.next=temp; node2=node2.next; } tail=tail.next; } if(node1!=null){ tail.next=node1; } else{ tail.next=node2; } return dummynode.next; } }

Gavisic + 3 comments why this give runtime error in tc5 and tc6

`if (head1==None and head2==None): return None if(head1==None): return head2 if (head2==None): return (head1) if head1.data<=head2.data: head1.next=mergeLists(head1.next,head2) else: temp = head2 head2 = head2.next temp.next=head1 head1=temp head1.next = mergeLists(head1.next,head2) return head1`

atomkevich + 0 comments do you find the answer on this question?

schiebermc + 0 comments You are hitting python's default recursion limit (which is quite conservative). Either revert your implementation into loops or use

`sys.setrecursionlimit()`

to increase the recursion depth.schiebermc + 0 comments [deleted]

Ankita4297 + 0 comments simple c++ code

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

Sort 437 Discussions, By:

Please Login in order to post a comment