题目

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

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

示例1：

image.png

输入：l1 = [7,2,4,3], l2 = [5,6,4]
输出：[7,8,0,7]
示例2：

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[8,0,7]
示例3：

输入：l1 = [0], l2 = [0]
输出：[0]

提示：

链表的长度范围为 [1, 100]
0 <= node.val <= 9
输入数据保证链表代表的数字无前导 0

java代码：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        List<Integer> list1 = appendToList(l1);
        List<Integer> list2 = appendToList(l2);

        ListNode head = null;
        int carry = 0;
        ListNode tail = null;
        int len1 = list1.size() - 1;
        int len2 = list2.size() - 1;
        while (len1 >= 0 || len2 >= 0 || carry > 0) {
            int n1 = len1 >= 0 ? list1.get(len1) : 0;
            int n2 = len2 >= 0 ? list2.get(len2) : 0;
            int sum = n1 + n2 + carry;
            if (head == null) {
                head = tail = new ListNode(sum % 10);
            } else {
                tail.next = new ListNode(sum % 10);
                tail = tail.next;
            }

            carry = sum / 10;
            len1 --;
            len2--;
        }

        return reverse(head);

    }

    private ListNode reverse(ListNode head) {
        ListNode reverseHead = null;
        ListNode temp = head;
        ListNode pre = null;
        while(temp!=null) {
            ListNode next = temp.next;
            if(next ==null) {
                //到头了
                reverseHead = temp;
            }

            temp.next = pre;

            pre = temp;
            temp = next;
        }

        return reverseHead;
    }

    private List<Integer> appendToList(ListNode l1) {
        List<Integer> list = new ArrayList<Integer>();
        while (l1 != null) {
            list.add(l1.val);
            l1 = l1.next;
        }
        return list;
    }
}