Tuesday, September 3, 2013

Add Two number represented as Link List

You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

    ListNode* getnode(int x)
 {
  ListNode *head  = (ListNode *)malloc(sizeof(ListNode));
  head->val = x;
  head->next = NULL;
  return head;
 }

    ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
  if(!l1)
   return l2;

  if(!l2)
   return l1;

  ListNode *head = NULL;
  ListNode *prev = NULL;
  int carry = 0;
  while(l1 && l2)
  {
   int sum  = l1->val + l2->val + carry;
   carry = sum / 10;
   sum = sum % 10;

   ListNode *newnode  = getnode(sum);
   if(!head)
   {
    head = newnode;
    prev = head;
   }
   else
   {
    prev->next = newnode;
    prev = prev->next;
   }

   l1 = l1->next;
   l2 = l2->next;
  }

  while(l1)
  {
   int sum  = l1->val + carry;
   carry = sum / 10;
   sum = sum % 10;

   ListNode *newnode  = getnode(sum);
   prev->next = newnode;
   prev = prev->next;

   l1 = l1->next;
  }

  while(l2)
  {
   int sum  = l2->val + carry;
   carry = sum / 10;
   sum = sum % 10;

   ListNode *newnode  = getnode(sum);
   prev->next = newnode;
   prev = prev->next;

   l2 = l2->next;
  }


  if(carry)
   prev->next = getnode(carry);

  return head;
}

No comments:

Post a Comment