[LeetCode] 2. Add Two Numbers (M

2. Add Two Numbers （c++)

  You are given two non-empty linked lists representing two non-negative integers. 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.

  You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example:

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

题意：给两个非空链表，表示两个非负整数。数字存储方式与数字顺序相反（即向右进位），每个节点都包含一个数字。将两个数字相加，并将其作为链表返回。

思路：新建一个链表res；每一位相加，以变量carry保存是否进位，保存每一位相加的结果sum在res链表上。最后一位判断carry是否为1，是的话res链表再添一个val为1的节点。

class Solution {
 public:
  ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
    ListNode *res = new ListNode(0);
    ListNode *cur = res;
    int sum = 0;
    int carry = 0;
    while (l1 || l2) {
      int n1 = l1->val ? l1->val : 0;
      int n2 = l2->val ? l2->val : 0;
      sum = n1 + n2 + carry;
      carry = sum / 10;
      cur->next = new ListNode(sum % 10);
      cur = cur->next;
      if (l1) {
        l1 = l1->next;
      }
      if (l2) {
        l2 = l2->next;
      }
    }
    if (carry) {
      cur->next = new ListNode(1);
    }
    return res->next;
  }
};