leetcode2.两数相加

题目：

给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例：

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/add-two-numbers

解法一：

首先想到的是使用递归来做，首先确定终止条件，是否到达链表尾部（l1和l2均到达），并且判断尾部是否大于10。之后对ListNode进行操作。首先补齐l1和l2中较短的链表，之后再相加并判断是否大于10。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* l;
        int sum = l1->val + l2->val;
        if(l1->next == NULL && l2->next == NULL){
            if(sum >= 10){
                sum-= 10;
                l = new ListNode(sum);
                l->next = new ListNode(1);
                return l;
            }
            else
                return new ListNode(sum);
        }
            
        else{
            if(l1->next == NULL)
                l1->next = new ListNode(0);
            if(l2->next == NULL)
                l2->next = new ListNode(0);
            if(sum >= 10){
                sum = sum - 10;
                l1->next->val++;
            }
            l = new ListNode(sum);
            l->next = addTwoNumbers(l1->next, l2->next);
            return l;
        }
    }
};

解法二：

但递归效率不高，因此可将其改为循环迭代来实现

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

        ListNode *node1 = l1;
        ListNode *node2 = l2;
        ListNode *newNode = NULL;
        ListNode *current = NULL;
        int carry = 0;
        while (node1 || node2) {
            int val1 = node1 ? node1->val : 0;
            int val2 = node2 ? node2->val : 0;
            int sum = val1 + val2 + carry;
            int val = sum % 10;
            carry = sum / 10;
            if (!newNode) {
                newNode = new ListNode(val);
                current = newNode;
            }
            else {
                current->next = new ListNode(val);
                current = current->next;
            }
            node1 = node1 ? node1->next : NULL;
            node2 = node2 ? node2->next : NULL;
        }

        if (carry) {
            current->next = new ListNode(carry % 10);
        }

        return newNode;
    }
};