Problem: Nodes in a list represent a number. For example, the nodes in Figure 1 (a) and (b) represent numbers 123 and 4567 respectively. Please implement a function/method to add numbers in two lists, and store the sum into a new list.
Read full article from Coding Interview Questions: No. 40 - Add on Lists
ListNode* Add(ListNode* pHead1, ListNode* pHead2)
{
if(pHead1 == NULL || pHead2 == NULL)
return NULL;
pHead1 = Reverse(pHead1);
pHead2 = Reverse(pHead2);
ListNode* pResult = AddReversed(pHead1, pHead2);
return Reverse(pResult);
}
ListNode* AddReversed(ListNode* pHead1, ListNode* pHead2)
{
int carry = 0;
ListNode* pPrev = NULL;
ListNode* pHead = NULL;
while(pHead1 != NULL || pHead2 != NULL)
{
ListNode* pNode = AddNode(pHead1, pHead2, &carry);
AppendNode(&pHead, &pPrev, pNode);
if(pHead1 != NULL)
pHead1 = pHead1->m_pNext;
if(pHead2 != NULL)
pHead2 = pHead2->m_pNext;
}
if(carry > 0)
{
ListNode* pNode = CreateListNode(carry);
AppendNode(&pHead, &pPrev, pNode);
}
return pHead;
}
ListNode* AddNode(ListNode* pNode1, ListNode* pNode2, int* carry)
{
int num1 = 0;
if(pNode1 != NULL)
num1 = pNode1->m_nValue;
int num2 = 0;
if(pNode2 != NULL)
num2 = pNode2->m_nValue;
int sum = num1 + num2 + *carry;
*carry = (sum >= 10) ? 1 : 0;
int value = (sum >= 10) ? (sum - 10) : sum;
return CreateListNode(value);
}
