其他
615，双指针解两数相加
问题描述
来源：LeetCode第2题
难度：中等
给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字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
题目数据保证列表表示的数字不含前导零
双指针解决
两个链表分别代表两个数字，链表的头节点表示的是个位数，如果从链表的头节点开始相加，符合我们常见的加法运算。
我们可以使用两个指针，开始的时候分别指向两个链表的头节点。用他们相加和的个位数构造一个新的节点（因为一个节点只能存储一位数字），这两个指针每次运算完之后都要同时往后移一步，然后还要使用一个变量carry表示是否有进位。两个指针只要有一个不为空，或者carry不为0就继续循环，我们看个视频。
来看下代码
public ListNode addTwoNumbers(ListNode listNode1, ListNode listNode2) {
//创建一个哑节点，他的指针指向新链表的头节点
ListNode dummyNode = new ListNode(0);
//preNode表示当前节点的前一个节点
ListNode preNode = dummyNode;
//表示两个节点相加进位的值，加法最多只进一位，所以carry要么是1要么是0
int carry = 0;
//两个链表只要有一个不为空，或者有进位就一直循环
while (listNode1 != null || listNode2 != null || carry != 0) {
//当前节点的累加值，需要加上前面进位的值
int sum = carry;
//如果第一个链表的当前节点不为空，加上第一个链表当前节点的值
if (listNode1 != null) {
sum += listNode1.val;
listNode1 = listNode1.next;
}
//第二个链表，同上
if (listNode2 != null) {
sum += listNode2.val;
listNode2 = listNode2.next;
}
//创建新的节点，preNode的next指针指向新的节点，因为链表节点
//只能存储一位数字，所以这里要对sum求余，取个位数。
preNode.next = new ListNode(sum % 10);
//如果sum大于等于10，说明有进位，carry为1，
//否则没有，carry为0
carry = sum / 10;
//更新preNode
preNode = preNode.next;
}
return dummyNode.next;
}
递归方式解决
这题其实没有什么难度，我们还可以改成递归的方式，原理和上面一样，都是从前往后加，递归的终止条件是两个链表都为空，并且没有进位。来看下代码
public ListNode addTwoNumbers(ListNode listNode1, ListNode listNode2) {
ListNode dummyNode = new ListNode(0);
helper(dummyNode, listNode1, listNode2, 0);
return dummyNode.next;
}
private void helper(ListNode preNode, ListNode listNode1, ListNode listNode2, int carry) {
//只有两个链表都为空并且没有进位的时候才终止循环
if (listNode1 == null && listNode2 == null && carry == 0)
return;
int sum = carry;
//链表1中节点的值累加
if (listNode1 != null) {
sum += listNode1.val;
listNode1 = listNode1.next;
}
//第二个链表，同上
if (listNode2 != null) {
sum += listNode2.val;
listNode2 = listNode2.next;
}
//创建新的节点
preNode.next = new ListNode(sum % 10);
//更新carry
carry = sum / 10;
//继续递归
helper(preNode.next, listNode1, listNode2, carry);
}
截止到目前我已经写了600多道算法题了，为了方便大家阅读，我把部分算法题整理成了pdf文档，目前有1000多页，大家可以在下面公众号“数据结构和算法”中回复关键字“pdf”即可获取下载链接。