【LeetCode刷题】2两数相加

LeetCode刷题】2两数相加"/>

【LeetCode刷题】2两数相加

2. 两数相加

JAVA代码

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

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

你可以假设除了数字 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
• 题目数据保证列表表示的数字不含前导零

方法一：模拟

初等数学

• 我们使用变量来跟踪进位，并从包含最低有效位的表头开始模拟逐位相加的过程。
• 对两数相加方法的可视化:342+465 = 807，每个结点都包含一个数字，并且数字按位逆序存储。

复杂度分析

• 时间复杂度:O(max(m,n))，假设m和n分别表示 1 1 1_1 11​和 1 2 1_2 12​的长度，上面的算法最多重复max(m，n)次
• 空间复杂度:O(max(m, n))，新列表的长度最多为max(m,n) + 1

class ListNode {int val;ListNode next;ListNode() {}ListNode(int val) { this.val = val; }ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

这里leetcode直接给出了链表定义方式，自己写千万知道咋写。这边给出了多种构造方法，方便使用。

class Solution {public ListNode addTwoNumbers(ListNode l1, ListNode l2) {ListNode head = null, tail = null;int carry = 0; //进位while (l1 != null || l2 != null) {int n1 = l1 != null ? l1.val : 0;int n2 = l2 != null ? l2.val : 0;int sum = n1 + n2 + carry;if (head == null) {head = tail = new ListNode(sum % 10);} else {tail.next = new ListNode(sum % 10);tail = tail.next;}carry = sum / 10;if (l1 != null) {l1 = l1.next;}if (l2 != null) {l2 = l2.next;}}if (carry > 0) {tail.next = new ListNode(carry);}return head;}
}

这边看下代码，这是官网给出的答案。
在方法中，首先定义了一个ListNode head和ListNode tail，定义进位为carry=0。
当l1和l2有一个不为空时，进行循环遍历，当l1不为空的时候，将l1的值赋给n1，如果为空的话，则给n1赋0，n1就是当前指针指向的值，同理，对于l2也定义一个n2，用来存放当前指针指向的值。sum就是加的和。这里为什么加上进位？例子342+465 = 807，当我们进行4+6=10，有一个进位carry=1，这个1需要加给下一个指针指向的值。
如果head为空，则将head和tail都赋值为当前加的和sum；否则，就将当前的sun存入到尾指针中，尾指针在指向下一个。进位为sum的十位上的数，通过整除10获得；如果l1和l2不为空，指针就接着指向下一个。如此循环，直到循环当前l1和l2都为空结束循环。
如果最后的进位carry大于0，想象一下56+53=109，指针逆着算，5+5是有进位的，此时，再加个尾指针，值为进位carry。
最后返回头指针head。
下面按代码进行了简单走一遍，方便理解。

方法二：添加初始值0

class Solution {public ListNode addTwoNumbers(ListNode l1, ListNode l2) {ListNode dummyHead = new ListNode(0);ListNode current = dummyHead;int carry = 0;while (l1 != null || l2 != null) {int x = (l1 != null) ? l1.val : 0;int y = (l2 != null) ? l2.val : 0;int sum = x + y + carry;carry = sum / 10; // 计算进位current.next = new ListNode(sum % 10);current = current.next;if (l1 != null) l1 = l1.next;if (l2 != null) l2 = l2.next;}if (carry > 0) {current.next = new ListNode(carry);}return dummyHead.next;}public static void main(String[] args) {ListNode l1 = new ListNode(2);l1.next = new ListNode(4);l1.next.next = new ListNode(3);ListNode l2 = new ListNode(5);l2.next = new ListNode(6);l2.next.next = new ListNode(4);Solution s = new Solution();ListNode result = s.addTwoNumbers(l1, l2);System.out.println(result.next.next.val);System.out.println(result.next.val);System.out.println(result.val);}
}