Dark_Knight19 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 Can u explain ur code?
Dark_Knight19 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 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 Umm yeah i think i forgot that .... thanks for pointing it out :)
wemiao 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 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 You are right. We can just have:
if(headA == NULL){ return headB; } else if(headB == NULL){ return headA; }
pvamsi4b3 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 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; } }
jatinkr30 Thanks
hooni 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;
nikhilausta please send de solution
vishal546 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;
thongcak 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 The question says A and B are already sorted.
zelataino 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.
etayluz 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 First check (headA == NULL && headB == NULL) is not necessary because the following two will handle it.
agodfrey3 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 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 I believe you can set nextB = headA->next at once and skip the extra step of changing the pointer with headB->next.
himanshusharmah1 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 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 Nicely done!!
neelmohapatra 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 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 [deleted]
EmberQuill 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 didn't work
ibarry Can you please explain your code?
pulekar_aditya Sweet..nice solution!
peta_vinay wow so simple to understand
piyushmishra amazing
ElizaW This is pretty!
nish456 What's the time complexity of your solution?
lose311 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 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 [deleted]tschul 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 [deleted]
whoiscris 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 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 Can you please explain your code by taking an example?? I am new to recursion.
kamaldheeraj 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 awesome.. thank you so much
thomas_doutre 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 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 how else if part of code work ,plss explain.
blackL 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 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 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. }
Prashant_meena 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 Thanks for this nice and easy to understand solution.
prachidwivedi why you wrote it as merged.next instead of merged simply.
prachidwivedi why you wrote it as merged.next
mugeesh 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 Why this is not working , can anybody give me the explaination please
suck_it headA->next = MergeLists(headA->next, headB); can you explain the meaning of this line/
pooleapply 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 Superb!
ak3933 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_ Thank you @Dark_Knight19 for giving the solution here only, god bless you bro.
vikasbaghel26 Nice code..!!
psyentist [deleted]
Vivic 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 instead of else if in last section it should be only else.
calvin_k_stone 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 This is pretty clean ! Thanks
omike1900 pretty easy to undarstand, awesome!
hbzahid Good job. You can get rid of the first if condition though. It seems redundant.
omar_s_mustafa [deleted]arunkumar_123 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 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 [deleted]abidkhan484 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 @DanHaggard If you use the
keyargument inmin/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
ebram_tharwat This is pretty cool. It also works fine if you converted it to JS
rshaghoulian 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 can you explain how the remaining elements are getting attached??
rshaghoulian 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.
rshaghoulian 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 The runtime is not O(n), but O(N+M), because you have to go through both lists in the worst case.
rshaghoulian I agree. Fixed. Thanks.
JordanT But taking X := MAX(N,M) means we can say O(2X) -> O(X) == O(N) Therefore it is O(N).
Right?
rshaghoulian 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 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).
rshaghoulian Yes, in your runtime analysis, if you set N = the larger of N, M, then your runtime is O(N).
JordanT So you were correct in your original analysis. The correction from O(N) to O(N+M) is wrong.
rshaghoulian 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 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 Can you please explain your code taking an example?
rshaghoulian Hi. I added an example for you to my original post above. Hope it helps.
bhuvnesh_kumar 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.
rshaghoulian 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 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.
rshaghoulian 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 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; }
luca_guarro wow okay thanks :)
akshitagarwal11 Thank You bro you helped me A lot
kewltek [deleted]sicter 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 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.
rshaghoulian 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 [deleted]
imaginationsuper 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 @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 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 Really nice solution and a easy to one to remember.
vivek_23 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 :|
kaosreigns 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 [deleted]
vedvasa 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
Parthasch // This is a "method-only" submission. // You only need to complete this method Node head; if(headA==null) return headB; if(headB==null) return headA; if(headA.data<headB.data) { head=headA; head.next=MergeLists(headA.next,headB); } else { head=headB; head.next=MergeLists(headB.next,headA); } return head;}
possen 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
Er_aditya A easy to understand code (using extra memory to create a newNode at each Recursion Call ).
Node MergeLists(Node headA, Node headB) { Node newNode = new Node(); if(headB== null) return headA; if (headA== null) return headB; if(headA==null && headB==null) return newNode; if( headA.data<=headB.data) { newNode.data=headA.data; newNode.next=MergeLists(headA.next,headB); } else { newNode.data=headB.data; newNode.next=MergeLists(headA,headB.next); } return newNode; }
amcodehard Simple non recursive solution:
Node MergeLists(Node headA, Node headB) { if(headA==null || headB == null) return headA==null?headB:headA; Node list=null; if(headA.data < headB.data){ list = headA; } else { list = headB; headB= headA; headA=list; } while(headA.next!=null){ if(headA.next.data > headB.data){ Node next = headA.next; headA.next=headB; headB= next; } headA= headA.next; } if(headA.next==null) headA.next = headB; return list; }
wuxi9007 I could not come up with an elegant solution as you did. Here is mine:
Node MergeLists(Node headA, Node headB) { Node merge; Node head; if(headA == null){ return headB; }else if(headB == null){ return headA; }else{ if(headA.data < headB.data){ merge = headA; headA = headA.next; }else{ merge = headB; headB = headB.next; } head = merge; } while(headA != null || headB != null){ if(headA == null){ merge.next = headB; break; }else if(headB == null){ merge.next = headA; break; }else{ if(headA.data < headB.data){ merge.next = headA; headA = headA.next; }else{ merge.next = headB; headB = headB.next; } merge = merge.next; } } return head; }
rmadhusudan359 @wuxi9007 could you help with my code, i'm able to get only the end elements, but not the middle ones.
Node* MergeLists(Node *headA, Node* headB) { // This is a "method-only" submission. // You only need to complete this method Node *temp, *headFinal; if( headA!= NULL && headB != NULL ){ if( headA->data < headB->data ) headFinal = headA; else headFinal = headB; }else if( headA != NULL ){ headFinal = headA; }else headFinal = headB; temp = headFinal; while( headA!= NULL && headB != NULL ){ if( headA->data < headB->data ){ temp->next = headB; headA = headA->next; }else{ temp->next = headA; headB = headB->next; } } return headFinal; }
wuxi9007 I think your problem is the pointer reference "temp = headFinal", since you are using C++, once you change temp->next, it actually changes headFinal->next as well. As you can imagine, at the end of the while loop, your headFinal only points to end elements.
Sort 326 Discussions, By:
Please Login in order to post a comment