2 两数相加

题目描述

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

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

示例

示例一输入：l1 = [2,4,3], l2 = [5,6,4]输出：[7,0,8]解释：342 + 465 = 807.示例二输入：l1 = [0], l2 = [0]输出：[0]示例三输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]输出：[8,9,9,9,0,0,0,1]

题解

由题目可知：用两个非空链表分别表示两个非负整数，计算两个数的和，例如链表2-4-3 则表示整数342，链表5-6-4则表示整数465，这样342+465=807，转换成链表就是7-0-8。

读懂了题目之后就知道只需要使用小学时学的通过竖式计算和的知识就能够计算出答案，竖式在计算时就是从两个数的个位开始相加，两个数相加满十进一，而且题目中的链表又刚好是以数字的逆序方式表示的，这样的话就只需要从两个链表的头节点开始相加，然后使用一个临时变量来存储进位的值，在两个节点相加时直接判断相加是否大于9，如果大于9的则将两个节点相加的和取余10则是当前位的值，两个节点相加的和除以10则是进位的值。

例如有节点node1的值为8和节点node2的值为5，两个节点相加的和为13，13大于9需要进位，则13 % 10 = 3，3就是当前位上的值，13 / 10 = 1，1就是进位的值。

注意点一：需要注意的是从链表的第二个节点开始计算的时候就需要判断是否有进位，如果有的话还要加上进位的值之后再判断是否大于9，这样还需要多一步来判断是否需要加上进位的值，所以更简单的方法就是将进位的初始值设为0，从第一个节点开始每次都加上进位的值，如果是0加上也没有影响。

注意点二：在对链表进行节点遍历相加时，可能会存在链表循环完了，但是还存在有进位的情况，所以最后需要判断进位上的值是不是0，如果不是0就还需要在结果链表的最后额外加上一个进位的节点。

注意点三：每一次循环之后都需要将存储进位的变量和存储两个节点相加和的临时变量清零。

注意点四：定义一个最终结果链表result之后，还需要有一个临时链表来代替result每一次的后移。

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {  ListNode i1 = l1;  ListNode i2 = l2;  // 定义最终答案链表  ListNode result = new ListNode();  // 定义临时链表代替result后移  ListNode tempNode = result;  // 定义存储进位的变量，默认为0  int carry = 0;  // 循环两个链表  while (i1 != null || i2 != null) {    // 定义临时存储两个节点和的变量    int temp = 0;    // 由于两个链表的长度可能不一致，所以需要分别判断两个链表当前节点是否为空，不为空则将当前节点的值加到变量temp上    if (i1 != null) {      temp += i1.val;      i1 = i1.next;    }    if (i2 != null) {      temp += i2.val;      i2 = i2.next;    }    // temp加上存储进位信息的carry    temp += carry;    // 当temp > 9时，temp / 10得到进位值，temp % 10得到当前位的值，如果不大于9，则将carry清零    if (temp > 9) {      carry = temp / 10;      temp %= 10;    } else {      carry = 0;    }    // 将temp生成一个节点node    ListNode node = new ListNode(temp);    // tempNode指向node    tempNode.next = node;    // tempNode后移一位    tempNode = node;  }  // 当两个链表都循环完之后判断carry是否不等于0，如果不等于0，则将carry生成一个节点，放到表示答案链表的最后面  if (carry != 0) {    ListNode end = new ListNode(carry);    tempNode.next = end;  }  // 由于在循环中第一次就是将值赋值给了tempNode的下一个节点，也就是result的下一个节点，所以返回时需要返回result.next  return result.next;}

关注专栏，持续更新……
公众号：良猿