题目

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/add-two-numbers

题目示例

解题思路

• 遍历两个链表，计算对应节点的和
• 设置一个进位，用来记录节点和的进位

难点

• 进位变量的设置，是一个技巧
• 节点指针的转换，编程时需要注意
• 代码边界需要特别注意

示例

  public class AddTwoNumbers {

    /**
     * 两个链表相加（简单版本）
     * 设置一个变量存储进位 carry
     * 开始：P = l1 , q = l2
     * 结束: p == null && q == null
     * 核心：p.val + q.val + carry
     *
     * @param l1
     * @param l2
     * @return
     */
    public ListNode addTwoNumbersV2(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }

        ListNode newHead = new ListNode();
        ListNode tail = newHead;
        ListNode p = l1;
        ListNode q = l2;
        int carry = 0;

        while (p != null || q != null || carry != 0) {
            int sum = 0;
            if (p != null) {
                sum = sum + p.val;
                p = p.next;
            }
            if (q != null) {
                sum = sum + q.val;
                q = q.next;
            }

            sum = sum + carry;
            tail.next = new ListNode(sum % 10);
            tail = tail.next;
            carry = sum / 10;
        }

        return newHead.next;
    }
}