We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
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).
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).
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.
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.
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.
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.
Merge two sorted linked lists
You are viewing a single comment's thread. Return to all comments →
Can u explain ur code?
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).
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)
Umm yeah i think i forgot that .... thanks for pointing it out :)
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).
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.
You are right. We can just have:
here is problem solution in python java c++ and c programming. https://solution.programmingoneonone.com/2020/07/hackerrank-merge-two-sorted-linked-lists-solution.html
for those who need it in java, here it is!
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; } }
did it work?
here is problem solution in python java c++ and c programming. https://solution.programmingoneonone.com/2020/07/hackerrank-merge-two-sorted-linked-lists-solution.html
Thanks
nice solution.
The latter part of the code can be slightly shortened:
Code post mat kar hero. bakiyo ko bhi karne de thodi mehnat.
@pvamsii43 what is the difference if you write the last else condition as given below?
I tried this code and it gave a non terminating output.
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; }
}
sugoi
SinglyLinkedListNode* mergeLists(SinglyLinkedListNode* head1, SinglyLinkedListNode* head2) {
} well..I think my code is easier to understand
where is mergeLists function
it is the main function thats we are calling again and again matlab recrusive
i don't think there is a need to check if both head1 and head2 are NULL.. question states that "either" may be NULL
please send de solution
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;
Can you please explain the else part
No problem! I give you best solution. In python the third.
please explain your code
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.
here is problem solution https://code.programmingoneonone.com/2020/09/get-node-value-solution-hackerrank.html
Then ..this is simpler version:-
As always Recursive approach is great.
yeah...you just need to understand recursion to be able to use it with ease.
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.
The question says A and B are already sorted.
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.
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; }
cant we do this firrst add all the elements and than sort it???
Did you get the answer of your question?
here is problem solution in java python c++ c and javascript programming. https://programs.programmingoneonone.com/2021/05/hackerrank-merge-two-sorted-linked-lists-solution.html