两数相加
题目描述
给出两个非空的链表用来表示两个非负的整数。其中,它们各自的位数是按照逆序的方式存储的,并且它们的每个节点只能存储一位数字。
如果,我们将这两个数相加起来,则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外,这两个数都不会以 0 开头。
示例
1 2 3
| 输入:(2 -> 4 -> 3) + (5 -> 6 -> 4) 输出:7 -> 0 -> 8 原因:342 + 465 = 807
|
题目来源:力扣(LeetCode)
题目链接:https://leetcode-cn.com/problems/add-two-numbers
题目著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
解法一
这道题主要考的就是合并两个链表,但是在合并的时候还要注意进位的问题,合并完成后也要考虑是否还有进位。
我第一次提交时,为了方便把合并链表的过程简写了,但是耗时好像有点高,只超过了 27 % 的提交(其实也就用了 3 ms):
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
|
class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode result = new ListNode(); ListNode root = result; int carry = 0; while (l1 != null || l2 != null) { int v1 = l1 == null ? 0 : l1.val; int v2 = l2 == null ? 0 : l2.val; int temp = v1 + v2 + carry; carry = temp / 10; result.next = new ListNode(temp % 10); result = result.next; l1 = l1 == null ? null : l1.next; l2 = l2 == null ? null : l2.next; } if (carry > 0) { result.next = new ListNode(carry); result = result.next; } return root.next; } }
|
随后我把合并的过程拆分开了,主要是减少了判断两个链表是否为空的次数,耗时减少到了 2 ms:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42
|
class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode result = new ListNode(); ListNode root = result; int carry = 0; while (l1 != null && l2 != null) { int temp = l1.val + l2.val + carry; carry = temp / 10; result.next = new ListNode(temp % 10); result = result.next; l1 = l1.next; l2 = l2.next; } while (l1 != null) { int temp = l1.val + carry; carry = temp / 10; result.next = new ListNode(temp % 10); result = result.next; l1 = l1.next; } while (l2 != null) { int temp = l2.val + carry; carry = temp / 10; result.next = new ListNode(temp % 10); result = result.next; l2 = l2.next; } if (carry > 0) { result.next = new ListNode(carry); result = result.next; } return root.next; } }
|