Monday, July 6, 2015

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)

No comments:

Post a Comment