tag:blogger.com,1999:blog-4228859841453048938.post3646599669054930849..comments2024-03-29T15:50:59.980+08:00Comments on Coding Interview Questions: No. 40 - Add on ListsHarry Hehttp://www.blogger.com/profile/10363303096963693183noreply@blogger.comBlogger12125tag:blogger.com,1999:blog-4228859841453048938.post-79092917114618855852017-08-02T06:14:30.293+08:002017-08-02T06:14:30.293+08:00Instead of appending nodes + final reversal of thi...Instead of appending nodes + final reversal of third list, try prepending nodes to make third list (no reversal needed then).<br /><br />Also, a littler simpler to prepend not append :)hamlethttps://www.blogger.com/profile/13334290641536314804noreply@blogger.comtag:blogger.com,1999:blog-4228859841453048938.post-31276432914093052992017-07-10T01:14:23.624+08:002017-07-10T01:14:23.624+08:00The stated question doesn't make sense. What a...The stated question doesn't make sense. What are you trying to do? Add all the nodes? Sum the nodes with corresponding indices?Anonymoushttps://www.blogger.com/profile/13748071083855097811noreply@blogger.comtag:blogger.com,1999:blog-4228859841453048938.post-9069944351038042022016-11-27T14:37:29.518+08:002016-11-27T14:37:29.518+08:00It makes sense to reverse the operand-lists for re...It makes sense to reverse the operand-lists for reasons best known. However, we might want to still consider the possibility of getting away with the idea of reversing the final resultant list. That list is now synthesized here by inserting the running result node at the head-end instead of where it is done hitherto. Evenutally, the head will naturally point to the highest place value. Having said that, illustrating with the very same example cited in this blog -<br /><br />We intend to add<br />List - A: 1->2->3<br />List - B: 4->5->6->7<br /><br />Now ordering the lists (exactly as per the preferred original design) -<br />List - A: 3->2->1<br />List - B: 7->6->5->4<br /><br /><br />Synthesizing Resultant list<br />---------------------------<br />Head initialized to NULL, Carry to 0<br />Carry = 0; Resultant_list->NULL<br /><br />Now, lets start pushing the results one by one on to the Resultant_list:<br />List - A: 3->2->1<br />List - B: 7->6->5->4->0<br /><br />Resultant_list->0->NULL<br />List - A: 2->1<br />List - B: 6->5->4->0<br />Carry = 1<br /><br />Resultant_list->9->0->NULL<br />List - A: 1<br />List - B: 5->4->0<br />Carry = 0<br /><br />Resultant_list->9->0->NULL<br />List - A: 1<br />List - B: 5->4->0<br />Carry = 0<br /><br />Resultant_list->6->9->0->NULL<br />List - A: NULL<br />List - B: 4->0<br />Carry = 0<br /><br />Resultant_list->4->6->9->0->NULL<br />List - A: NULL<br />List - B: 4->0<br />Carry = 0<br /><br />Resultant_list[head]->4->6->9->0->NULL<br /><br />So in effect, we have actually done away with the final reversal that was needed earlier; note that the Resultant_list is already formed in right order. And now, with that philosophy, lets turn back at the original code and get it simplified as under -<br /><br />ListNode* Add (ListNode* pHead1, ListNode* pHead2)<br />{<br />if (pHead1 == NULL || pHead2 == NULL)<br />return NULL;<br /><br />pHead1 = Reverse(pHead1);<br />pHead2 = Reverse(pHead2);<br />return AddReversed(pHead1, pHead2);<br />}<br /><br />ListNode* AddReversed (ListNode* pHead1, ListNode* pHead2)<br />{<br />int carry = 0;<br />ListNode* pHead = NULL;<br /><br />while(pHead1 != NULL || pHead2 != NULL)<br />{<br />ListNode* pNode = AddNode(pHead1, pHead2, &carry);<br />AppendNode(&pHead, pNode);<br /><br />if(pHead1 != NULL)<br />pHead1 = pHead1->m_pNext;<br />if(pHead2 != NULL)<br />pHead2 = pHead2->m_pNext;<br />}<br /><br />if(carry > 0)<br />{<br />ListNode* pNode = CreateListNode(carry);<br />AppendNode(&pHead, pNode);<br />}<br /><br />return pHead;<br />}<br /><br />ListNode* AddNode(ListNode* pNode1, ListNode* pNode2, int* carry)<br />{<br />int balance = *carry;<br />if (pNode1 != NULL) balance += pNode1->m_nValue;<br />if (pNode2 != NULL) balance += pNode2->m_nValue;<br />if (balance >= 10) {<br />balance -= 10;<br />*carry = 1;<br />} else *carry = 0;<br /><br />return CreateListNode(balance);<br />}<br /><br />void AppendNode(ListNode** pHead, ListNode* pNode)<br />{<br />if (!pHead) return;<br />if (!pNode) return;<br />pNode->m_pNext = *pHead;<br />*pHead = pNode;<br />}<br /><br />Well cool, that has relaxed us from reversing the result list as well as the headache of the additional node - pPrev that was maintained hitherto, further simplifying the amalgam of code at large.Anonymoushttps://www.blogger.com/profile/09275509938541101354noreply@blogger.comtag:blogger.com,1999:blog-4228859841453048938.post-6675965886564496332016-11-27T00:25:44.321+08:002016-11-27T00:25:44.321+08:00This comment has been removed by the author.Anonymoushttps://www.blogger.com/profile/09275509938541101354noreply@blogger.comtag:blogger.com,1999:blog-4228859841453048938.post-31746122221036335742016-11-27T00:07:57.368+08:002016-11-27T00:07:57.368+08:00This comment has been removed by the author.Anonymoushttps://www.blogger.com/profile/09275509938541101354noreply@blogger.comtag:blogger.com,1999:blog-4228859841453048938.post-34032240307991697092016-11-26T23:11:37.017+08:002016-11-26T23:11:37.017+08:00This comment has been removed by the author.Anonymoushttps://www.blogger.com/profile/09275509938541101354noreply@blogger.comtag:blogger.com,1999:blog-4228859841453048938.post-91386460001417176182015-10-18T01:49:14.876+08:002015-10-18T01:49:14.876+08:00Your solution is quick and easy, but what happens ...Your solution is quick and easy, but what happens if the linked list represents a number bigger than what an int/long/double can hold? <br />Your solution won't work anymore, and this is what the interviewer is really testing you for. Anonymoushttps://www.blogger.com/profile/12670292861395250800noreply@blogger.comtag:blogger.com,1999:blog-4228859841453048938.post-56955409244197805362015-09-18T12:46:19.338+08:002015-09-18T12:46:19.338+08:00I think it would be better to use a stack and add ...I think it would be better to use a stack and add the digits on topAnonymoushttps://www.blogger.com/profile/18078361990695643553noreply@blogger.comtag:blogger.com,1999:blog-4228859841453048938.post-43708285255629788222015-08-11T16:44:31.331+08:002015-08-11T16:44:31.331+08:00Why to do all the reverse and sum each digits and ...Why to do all the reverse and sum each digits and the maintain the carry for each iteration.? <br /><br />Why don't you simply traverse a list and make the number like 123 and from other list make number 4567<br /><br />simply add these number as integer and extract each number from result and make another list <br />Java For Interviewhttps://www.blogger.com/profile/12229904665416696428noreply@blogger.comtag:blogger.com,1999:blog-4228859841453048938.post-71176776679543635812014-05-09T02:33:06.520+08:002014-05-09T02:33:06.520+08:00The problem is if the numbers are very large. Wha...The problem is if the numbers are very large. What if you had lists with 100 entries? or 1000 entries?<br /><br />The point is that this should work with lists or arbitrary length.Anonymoushttps://www.blogger.com/profile/13770550726175533660noreply@blogger.comtag:blogger.com,1999:blog-4228859841453048938.post-87153962566945576992014-02-16T23:22:43.360+08:002014-02-16T23:22:43.360+08:00oh dear... is my formatting bad or what.... oh dear... is my formatting bad or what.... Zahohttps://www.blogger.com/profile/02359007812468852321noreply@blogger.comtag:blogger.com,1999:blog-4228859841453048938.post-15962458384838244192014-02-16T23:21:19.816+08:002014-02-16T23:21:19.816+08:00Hi there, I think this is a good solution. However...Hi there, I think this is a good solution. However.. If I were you I would actually avoid bothering with carrying the digits. The way to handle that is to convert each of the two lists into numbers and then add them. So you can have something like: <br /><br />int generateNumberFromList(Node* head) {<br /><br /> Node* revPtr = reverseMe(head);<br /><br /> int result = 0;<br /> int multiplier = 1;<br /> while(revPtr) {<br /> result = result + (revPtr->value * multiplier);<br /> multiplier = multiplier * 10;<br /> revPtr = revPtr->next;<br /> }<br />return result;<br />}<br /><br />Now that you can convert a list into a number, just go ahead and write a wrapper function to add them ;) <br /><br />int sumLists(Node* x, Node* y) {<br /> return generateNumberFromList(x) + generateNumberFromList(y);<br />}<br /><br />This way you can easily implement any numeric operation between numbers implemented as lists .. With your current approach addition is fairly easy to knock out.. but go ahead and try division... that would be quite error prone.. <br /><br />Anyway, just my to cents. Btw I really enjoy your blog and just got your book as well, nice work ! I like the questions because they are jus the right level of complexity. Keep it up ! <br />Zahohttps://www.blogger.com/profile/02359007812468852321noreply@blogger.com