两数相加

1、参考资料

https://leetcode-cn.com/problems/add-two-numbers/

2、题目要求

题目描述

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

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

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

示例：

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

3、代码思路

低位相加，有可能需要向高位进 1，所以我们添加 carry 变量，用于记录上次相加的结果是否需要向高位进位，carry = 0 表示不需要向高位进位，carry = 1 表示需要向高位进位

4、代码实现

代码

/** * @ClassName DddTwoNumbersDemo * @Description TODO * @Author Heygo * @Date 2020/9/3 12:47 * @Version 1.0 */ public class DddTwoNumbersDemo { public static void main(String[] args) { ListNode list1 = new ListNode(2); list1.next = new ListNode(4); list1.next.next = new ListNode(3); ListNode list2 = new ListNode(5); list2.next = new ListNode(6); list2.next.next = new ListNode(4); Solution solution = new Solution(); ListNode sumList = solution.addTwoNumbers(list1, list2); } } class Solution { /** * 两数相加 * @param list1 链表 1 * @param list2 链表 2 * @return 相加后的链表 */ public ListNode addTwoNumbers(ListNode list1, ListNode list2) { ListNode list1Pointer = list1; ListNode list2Pointer = list2; ListNode dummyHead = new ListNode(0); ListNode sumListPointer = dummyHead; int carry = 0; // 进位标志位，为 0 表示不进位，为 1 表示进位 int sum = 0; // 当前位的加和 while (list1Pointer != null || list2Pointer != null || carry != 0) { // list1Pointer 指针不为空 if (list1Pointer != null) { sum += list1Pointer.val; // 累加 list1Pointer = list1Pointer.next; // 指针后移 } // list2Pointer 指针不为空 if (list2Pointer != null) { sum += list2Pointer.val; // 累加 list2Pointer = list2Pointer.next; // 指针后移 } sum += carry; // 加上进位标志位 carry = sum / 10; // 获取本次的进位标志位（十位数） sum = sum % 10; // 获取当前位的值（个位数） sumListPointer.next = new ListNode(sum); // 创建新节点 sumListPointer = sumListPointer.next; // 指针后移 sum = 0; // 加和清零 } return dummyHead.next; } } class ListNode { int val; ListNode next; ListNode(int x) { val = x; } }