LeetCode第2题两数相加-java实现-图解思路与手撕代码
一、题目描述
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
二、解题思路
这道题给我们两个链表以及链表中节点的数据结构，每个链表表示一个数字，表现形式是第一项为个位数，第二项为十位数，往后依此类推，如下图所示，分别为三位数342和465。
现要求我们把这两个数字相加，然后以示例链表的表现形式返回输出。
最自然的思路是定义一个链表头和一个当前节点，链表头也正常存储数据，遍历两个给定的链表，对应位置相加，如果单个位置上相加的结果大于等于10就需要进位，然后在我们链表上当前位置存储相加结果的个位数，最后更新当前链表。
有三个值得注意的点：
1.链表头和链表的当前位置分开定义，链表头不能动，最后需要把这个返回输出，链表的当前位置在给val赋值之后不断指向next。
2.两个链表可能对不齐，会出现一个链表循环完毕了，另一个next还不为空的情况，这时候把循环完毕的链表用0代替，相加结果
三、代码实现
1.定义数据
首先定义一个当前节点cur，并用一个节点head指向该节点，后续我们会不断将cur后移，但head不变，最后返回head
然后定义一个变量carry表示是否需要进位。
代码如下（示例）：
ListNode cur = new ListNode();
ListNode head = cur;
int carry = 0;
2.相加部分实现
由于我们不需要返回示例链表，所以直接移动链表头就可以了，当两个链表头都为空的时候就可以退出循环了。
在循环中将两个链表头存储的数组相加，如果其中某个链表为空，就用0替代，对相加的结果进行判断，为进位标志位carry进行赋值。
随后给返回链表的当前节点存储数据，并根据两个链表头的next存在情况更新当前节点
代码如下（示例）：
while (l1 != null | l2 != null) {
int val1 = 0;
if (l1 != null) {
val1 = l1.val;
}
int val2 = 0;
if (l2 != null) {
val2 = l2.val;
}
int add = val1 + val2 + carry;
if (add >= 10) {
carry = 1;
add = add % 10;
} else {
carry = 0;
}
cur.val = add;
if (l1 != null) {
l1 = l1.next;
}
if (l2 != null) {
l2 = l2.next;
}
if (l1 != null | l2 != null) {
cur.next = new ListNode();
cur = cur.next;
}
}
循环结束后需要再此判断进位标志位是否为1，如果为1则表示需要再做一次相加操作。
if (carry==1){
cur.next=new ListNode(carry);
}
总结
该方法简单易于理解，时间复杂度低
但是代码比较冗余，有优化空间。