【刷题记录】2. 两数相加

一、题目描述

来源 

LeetCode

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

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

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

示例 1：

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

解释：342 + 465 = 807.

示例 2：

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

示例 3：

输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9] 输出：[8,9,9,9,0,0,0,1]

提示：

• 每个链表中的节点数在范围 [1, 100] 内

• 0 <= Node.val <= 9

• 题目数据保证列表表示的数字不含前导零

二、思路分析：

这个题目我们实质上可以把它看做成一个数学运算过程 

两个数相加的竖式运算过程

就像上面图片中

• l1 就是[3,4] l2 就是[7,2] 链表中对应位置的相加，
  就是数字运算过程中，由低位向高位相加的一个过程。

• 如果相加有进位数时候，我们要记录进位数，并且在一次的运行中相加上这个进位数 就是上图中的
  1（tens）

• 然后把每次的结果存入到一个新的链表中 比如上图中结果为70 就是 [0,7]

三、代码实现

 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; }
 }
 public ListNode addTwoNumbers(ListNode l1, ListNode l2) {

 // 输出结果的链表
 ListNode resultNode = new ListNode(0);
 ListNode head = resultNode;
 // 记录进位数
 int carryNum = 0;

 while (l1 != null || l2 != null){
 // 判断两个链表中对应位置是否存在值 （可能连个链表位数不一致）
 int num1 = l1 != null ? l1.val : 0;
 int num2 = l2 != null ? l2.val : 0;

 // 对应位置上的数字相加 以及加上进位数
 int tmpnum = num1 + num2 + carryNum;

 // 记录对应数字到链表
 head.next = new ListNode(tmpnum % 10 );

 //获取进位数
 carryNum = tmpnum / 10;

 head = head.next;

 if (l1 != null) l1 = l1.next;
 if (l2 != null) l2 = l2.next;

 }

 // 如果最高位还有进位 补位。
 if (carryNum > 0) head.next = new ListNode(carryNum);
 return resultNode.next;
 }
}


运行结果

总结

我们可以把问题转化为我们比较熟悉的一个模型，然后能更好的理解和想出解决的方式。