Amazon Question: Add two numbers represented by linked lists

Problem: Given two numbers represented by two linked lists, write a method that returns linked list representing the addition of two input numbers.

Solution: No need to explain. Can be easily understood by the implementation.

Implementation:

//All of these methods are friends to List class

void addAtFront(List::ListNode*& head, int num)

{

List::ListNode* newNode = new List::ListNode(num, head);

head = newNode;

}

void addCarry(List::ListNode* node1, List::ListNode* node2, int& carry, List::ListNode *&result)

{

if(node1 != node2)

{

addCarry(node1->next, node2, carry, result);

int sum = node1->data + carry;

carry = sum/10;

sum = sum % 10;

addAtFront(result, sum);

}

}

List::ListNode* addSameLenNum(List::ListNode* node1, List::ListNode* node2, int& carry)

{

if(!node1)

return NULL;

List::ListNode *node = new List::ListNode();

node->next = addSameLenNum(node1->next, node2->next, carry);

int sum = node1->data + node2->data + carry;

carry = sum / 10;

node->data = sum % 10;

return node;

}

List* addNum(List l1, List l2)

{

if(!l1.head)

{

return new List(l2);

}

if(!l2.head)

{

return new List(l1);

}

 List* result = new List()

List::ListNode *head1 = l1.head, *head2 = l2.head;

int len1 = l1.len, len2 = l2.len;

int carry = 0;

if(len1 == len2)

result->head = addSameLenNum(l1.head, l2.head, carry);

else

{

if(len1 < len2)

{

head1 = l2.head;

head2 = l1.head;

}

int diff = std::abs(len1 - len2);

List::ListNode* curr = head1;

for(int i = 0; i < diff; ++i, curr=curr->next);

result->head = addSameLenNum(curr, head2, carry);

addCarry(head1, curr, carry, result->head);

}

if(carry)

addAtFront(result->head, carry);

return result;

}

Complexity: O(n)