leetcode-[2]两数相加

leetcode 002两数相加(Medium)(链表)

leetcode-[2]两数相加(Medium)(链表)

题目说明

//给你两个 非空 的链表,表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的,并且每个节点只能存储 一位 数字。 
//请你将两个数相加,并以相同形式返回一个表示和的链表。
//你可以假设除了数字 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
// 题目数据保证列表表示的数字不含前导零
//
// Related Topics 递归 链表 数学

辅助代码(链表)

/**
* Definition for singly-linked list.
* 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; }
* }
*/

题目分析

对两个链表的相同指针的数据进行相加,如相加的结果大于10,则需要对下一位指针相加后的结果加1。

解题思路

方法一:递归累加法

  1. 对两个链表同时进行递归操作,将两个链表累加的值存入待输出的链表中
  2. 需要判断累加的值是否超过了10,如超过了10,则下一次递归的时候需要进位操作(即将结果在加1)
  3. 当某一个链表递归结束时,则递归终止,将另一方链表的剩余节点添加到待输出链表中。
  4. 时间复杂度: O(n)
/**
* 解题思路:
* 1.利用引用传值的特点,递归累加
* 2.bit表示数字相加和大于10的进位
* <p>
* 执行耗时:1 ms,击败了100.00% 的Java用户
* 内存消耗:41.1 MB,击败了10.30% 的Java用户
*/
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode rootNode = new ListNode();
// 递归操作,将结果保存在rootNode中
addTwoNumbers(rootNode, l1, l2, 0);
return rootNode;
}

/**
* 进行递归累加的方法
*
* @param node 待输出链表
* @param l1 链表1
* @param l2 链表2
* @param bit 进位标志,如果相加结果超过10,则该值为1
*/
private void addTwoNumbers(ListNode node, ListNode l1, ListNode l2, int bit) {
int l1Val = 0, l2Val = 0;
// 获取链表1的值
if (l1 != null) {
l1Val = l1.val;
l1 = l1.next;
}
// 获取链表2的值
if (l2 != null) {
l2Val = l2.val;
l2 = l2.next;
}

// 计算值相加
int val = l1Val + l2Val + bit;
bit = val / 10;
val %= 10;

// 相加结果取模后放入待输出链表中
node.val = val;

// 递归结束条件:所有链表遍历完成,且进位标记为0
if (l1 == null && l2 == null && bit == 0) {
return;
}
// 递归累加
ListNode nextNode = new ListNode();
node.next = nextNode;
addTwoNumbers(nextNode, l1, l2, bit);
}

总结

单链表中每个节点会存储下一个节点的指针,因此输出时只需要将头节点输出即可。