CTCI Question 2.5 - add linked lists
The answer in the book is not terribly compact, especially for part 2. Here is a better version in C++.
Node * list_add(Node * pN0, Node * pN1)
{
Node * pNReturn = nullptr;
Node ** ppNNext = & pNReturn;
unsigned carry = 0;
while (pN0 != nullptr || pN1 != nullptr || carry > 0)
{
unsigned sum = carry;
if (pN0 != nullptr)
{
sum += pN0->data;
pN0 = pN0->next;
}
if (pN1 != nullptr)
{
sum += pN1->data;
pN1 = pN1->next;
}
if (sum >= 10)
{
sum -= 10;
carry = 1;
}
else
{
carry = 0;
}
*ppNNext = new Node;
(*ppNNext)->data = sum;
(*ppNNext)->next = nullptr;
ppNNext = &(*ppNNext)->next;
}
return pNReturn;
}
// helper function
Node * list_reverse(Node * pNHead)
{
Node * pNRet = pNHead;
if (pNHead != nullptr && pNHead->next != nullptr)
{
Node * pN0 = pNHead, * pN1 = pNHead->next;
pN0->next = nullptr;
while (pN1 != nullptr)
{
Node * pNHold = pN1->next;
pN1->next = pN0;
pN0 = pN1;
pN1 = pNHold;
}
pNRet = pN0;
}
return pNRet;
}
// Now part 2 becomes a piece of cake
Node * list_add2(Node * pNHead0, Node * pNHead1)
{
return list_reverse(list_add(list_reverse(pNHead0), list_reverse(pNHead1)));
}