leetcode--445--两数相加 II

题目：
给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。

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

进阶：

如果输入链表不能修改该如何处理？换句话说，你不能对列表中的节点进行翻转。

示例：

输入：(7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 8 -> 0 -> 7

链接：https://leetcode-cn.com/problems/add-two-numbers-ii

思路：
1、将输入链表反转存储起来存储成列表。遍历两个列表，逐位相加

Python代码：

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        s1 = []
        s2 = []

        while l1:
            s1.append(l1.val)
            l1 = l1.next

        while l2:
            s2.append(l2.val)
            l2 = l2.next

        ret = None

        carry = 0
        while s1 or s2 or carry:
            sum = carry
            if s1:
                sum += s1.pop()
            if s2:
                sum += s2.pop()
            node = ListNode(sum%10)
            carry = sum/10
            node.next = ret
            ret = node
        return ret

C++代码：

/**
 * 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) {
        vector<int > s1;
        vector<int > s2;

        while(l1 != nullptr){
            s1.push_back(l1->val);
            l1 = l1->next;
        }
        while(l2 != nullptr){
            s2.push_back(l2->val);
            l2 = l2->next;
        }

        ListNode* ret = nullptr;
        int carry=0;
        while (s1.size()>0 || s2.size()>0 || carry>0){
            int sum = carry;
            if (s1.size()>0){
                int item = s1.back();
                s1.pop_back();
                sum += item;
            }
            if (s2.size()>0){
                int item = s2.back();
                s2.pop_back();
                sum += item;
            }
            ListNode* temp = new ListNode(sum%10);
            carry = sum/10;
            temp->next = ret;
            ret = temp;
        }
        return ret;
    }
};

Java代码：

import java.util.*;
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ArrayList<Integer> s1 = new ArrayList<Integer>();
        ArrayList<Integer> s2 = new ArrayList<Integer>();

        while(l1!=null){
            s1.add(l1.val);
            l1 = l1.next;
        }
        while(l2!=null){
            s2.add(l2.val);
            l2 = l2.next;
        }

        int carry=0;
        ListNode ret = null;
        while (s1.size()>0 || s2.size()>0 || carry>0){
            int sum=carry;
            if(s1.size()>0){
                int item = s1.get(s1.size()-1);
                sum += item;
                s1.remove(s1.size()-1);
            }
            if(s2.size()>0){
                int item = s2.get(s2.size()-1);
                sum += item;
                s2.remove(s2.size()-1);
            }
            ListNode temp = new ListNode(sum%10);
            carry = sum/10;
            temp.next = ret;
            ret = temp;
        }
        return ret;
    }
}