这是悦乐书的第340次更新，第364篇原创文章地址https://www.yii666.com/article/764056.html
01 看题和准备
今天介绍的是LeetCode算法题中Medium级别的第1题（顺位题号是2）。给定两个非空链表，表示两个非负整数。 数字以相反的顺序存储，每个节点包含一个数字。将两个数字相加并将其作为链表返回。你可以假设这两个数字不包含任何前导零，除了数字0本身。例如：
输入：（2 -> 4 -> 3）+（5 -> 6 -> 4）
输出：7 -> 0 -> 8
说明：342 + 465 = 807。文章来源地址:https://www.yii666.com/article/764056.html
本次解题使用的开发工具是eclipse，jdk使用的版本是1.8，环境是win7 64位系统，使用Java语言编写和测试。
02 第一种解法
计算链表的节点值之和，包含以下两种情况：
进位。两个节点值相加大于等于10后，会产生进位问题，需要将进位产生的数加到下一轮计算上去。如果是在最后一次计算产生进位，结果链表需要增加一个next节点。
两链表的长度不相等时，可能会有一个链表先遍历完节点，而另外一个还剩下许多节点没遍历，因此在遍历的循环条件处，判空是或的关系，直到两个链表的节点都遍历完，才结束循环。
在此解法中，我们使用一个新的链表(头节点值为0)作为结果链表，使用一个boolean类型的变量flag来当做是否有进位的标志。
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode result = new ListNode(0);
ListNode tem = l1;
ListNode tem2 = l2;
ListNode current = result;
boolean flag = false;
while (tem != null || tem2 != null) {
// 计算节点值之和，需要判空
int sum = (tem != null ? tem.val : 0) +
(tem2 != null ? tem2.val : 0);
// 有进位，节点值之和加1，flag变为false
if (flag) {
sum += 1;
flag = false;
}
// 节点值之和大于等于10，只保留个位数，flag变为true
if (sum >= 10) {
sum -= 10;
flag = true;
}
current.next = new ListNode(sum);
current = current.next;
if (tem != null) {
tem = tem.next;
}
if (tem2 != null) {
tem2 = tem2.next;
}
}
// 尾节点可能因进位而产生
if (flag) {
current.next = new ListNode(1);
}
return result.next;
}
03 第二种解法
思路和上面一样，只是将计算进位换了一种方式来实现，采用了取余和整除的方式来实现。
public ListNode addTwoNumbers2(ListNode l1, ListNode l2) {
ListNode result = new ListNode(0);
ListNode temp = result;
int count = 0;
while (l1 != null || l2 != null) {
int sum = (l1 == null ? 0 : l1.val) +
(l2 == null ? 0 : l2.val);
sum += count;
count = sum/10;
temp.next = new ListNode(sum%10);
temp = temp.next;
if (l1 != null) {
l1 = l1.next;
}
if (l2 != null) {
l2 = l2.next;
}
}
if (count > 0) {
temp.next = new ListNode(count);
}
return result.next;
}
04 第三种解法
使用递归。
public ListNode addTwoNumbers3(ListNode l1, ListNode l2) {
ListNode result = new ListNode(0);
helper(result, l1, l2, 0);
return result.next;
}
/**
* 递归方法
* @param result 结果链表
* @param l1
* @param l2
* @param carry 进位产生的数
*/
public void helper(ListNode result, ListNode l1, ListNode l2, int carry) {
if (l1 == null && l2 == null) {
return ;
}
int sum = (l1 == null ? 0 : l1.val) +
(l2 == null ? 0 : l2.val);
sum += carry;
carry = sum/10;
result.next = new ListNode(sum%10);
result = result.next;
if (l1 != null) {
l1 = l1.next;
}
if (l2 != null) {
l2 = l2.next;
}
if (l1 == null && l2 == null && carry > 0) {
result.next = new ListNode(carry);
}
helper(result, l1, l2, carry);
}
05 第四种解法
对上面的递归方法，我们还可以再简化下，不借助额外的递归方法，以此方法本身做递归。
public ListNode addTwoNumbers4(ListNode l1, ListNode l2) {
if (l1 == null && l2 == null) {
return null;
}
int val = (l1 == null ? 0 : l1.val) +
(l2 == null ? 0 : l2.val);
ListNode result = new ListNode(val%10);
result.next = addTwoNumbers4(l1 == null ? null : l1.next,
l2 == null ? null : l2.next);
if (val >= 10) {
result.next = addTwoNumbers4(result.next, new ListNode(1));
}
return result;
}
06 小结
算法专题目前已连续日更超过六个月，算法题文章209+篇，公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词，获取系列文章合集。
以上就是全部内容，如果大家有什么好的解法思路、建议或者其他问题，可以下方留言交流，点赞、留言、转发就是对我最大的回报和支持！网址:yii666.com