中文版本
题目
难度:中等
给出两个 非空 的链表用来表示两个非负的整数。其中,它们各自的位数是按照 逆序 的方式存储的,并且它们的每个节点只能存储 一位 数字。
如果,我们将这两个数相加起来,则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外,这两个数都不会以 0 开头。
示例:
输入:(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出:7 -> 0 -> 8
原因:342 + 465 = 807
解题思路
这题比较简单,直接用进位法做就可以了,但是边界条件还需要考虑清楚:
- 当一个列表比另一个列表长时
l1=[0,1],l2=[0,1,2],l2=[0,1,2]
- 当一个列表为空时,即出现空列表
l1=[],l2=[0,1],l2=[0,1]
- 求和运算最后可能出现额外的进位,这一点很容易被遗忘
l1=[9,9],l2=[1],l2=[1]
代码
Python3
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
dummy_head = ListNode(0)
curr = dummy_head
carry = 0
while l1 is not None or l2 is not None:
val1 = l1.val if l1 is not None else 0
val2 = l2.val if l2 is not None else 0
sum = carry + val1 + val2
curr.next = ListNode(sum % 10)
curr = curr.next
carry = 0 if sum < 10 else 1
l1 = l1.next if l1 is not None else None
l2 = l2.next if l2 is not None else None
if carry > 0:
curr.next = ListNode(carry)
return dummy_head.next
Java
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode dummyHead = new ListNode(0);
ListNode p = l1, q = l2, curr = dummyHead;
int carry = 0;
while (p != null || q != null) {
int x = (p != null) ? p.val : 0;
int y = (q != null) ? q.val : 0;
int sum = carry + x + y;
carry = sum / 10;
curr.next = new ListNode(sum % 10);
curr = curr.next;
if (p != null) p = p.next;
if (q != null) q = q.next;
}
if (carry > 0) {
curr.next = new ListNode(carry);
}
return dummyHead.next;
}
Go
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
dummyHead := &ListNode{0, nil}
p, q, curr := l1, l2, dummyHead
carry := 0
for p != nil || q != nil {
var x, y int
if p != nil {
x = p.Val
} else {
x = 0
}
if q != nil {
y = q.Val
} else {
y = 0
}
sum := x + y + carry
curr.Next = &ListNode{sum % 10, nil}
curr = curr.Next
if p != nil {
p = p.Next
} else {
p = nil
}
if q != nil {
q = q.Next
} else {
q = nil
}
if sum >= 10 {
carry = 1
} else {
carry = 0
}
}
if carry == 1 {
curr.Next = &ListNode{1, nil}
}
return dummyHead.Next
}
网友评论