2. Add Two Numbers

So now we have got two linked lists. and I suppose the defination of the nodes of the linked list is as follow.

first our node have a value, and it has a next, to point to its next.

struct ListNode{
    int val;
    ListNode *next;
    ListNode(x): val(x), next(NULL){}
};

so now we need to add the two lists together. I will do it by starting from the head of our lists, which is the lowest digit in our nums. then to the next of head, and the next until we reach the last digit. and i will need an integer to record the carry of the current two digs. the sum is also recorded in a linked-list, so we need to create the first node of the sum list.

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
      int carry = 0, tmp = 0;
      ListNode presum(0); ListNode *p = &presum;

      while (l1 || l2 || carry){
          if (l1){
              tmp += l1 -> val;
              l1 = l1 -> next;
          }
          if (l2){
              tmp += l2 -> val;
              l2 = l2 -> next;
          }
          tmp += carry;
          carry = tmp / 10;
          p -> next = new ListNode(tmp % 10);
          p = p -> next;
          tmp = 0;
      }

      return presum.next;
    }
};

• test

  • did carry be added
  • if one of the list becomes empty

give up using the dummy presum.

• should think of not using the carry
• should notice that without if (carry || l1 || l2) there would be a extra 0 on the end of the list

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
      int carry = 0, tmp = 0;
      ListNode *sum = new ListNode(0); 
      ListNode *p = sum;

      while (l1 || l2 || carry){
          if (l1){
              tmp += l1 -> val;
              l1 = l1 -> next;
          }
          if (l2){
              tmp += l2 -> val;
              l2 = l2 -> next;
          }
          tmp += carry;
          carry = tmp / 10;
          p -> val = tmp % 10;
          if (carry || l1 || l2){
              p -> next = new ListNode(0);
              p = p -> next;
          }
          tmp = 0;
      }

      return sum;
    }
};

someone else's recursive answer

class Solution {
    public:
        ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
            if (l1 == NULL) return l2; 
            if (l2 == NULL) return l1; 

            int a = l1->val + l2->val;
            ListNode *p = new ListNode(a % 10);
            p->next = addTwoNumbers(l1->next,l2->next);
            if (a >= 10) p->next = addTwoNumbers(p->next, new ListNode(1));
            return p;
        }
  };

おまけ

the difference between . and ->

箭头（->）：左边必须为指针；

点号（.）：左边必须为实体。

(*p)->nextequals to p.next