Last Updated: 2024-06-14 22:49:28 Friday
-- TOC --
从Title上看，LeetCode的题目似乎都很简单，但是其实并不是这样的。
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list. You may assume the two numbers do not contain any leading zero, except the number 0 itself.
输入是两个non-negative integers，但是表达方式比较怪异，用的是singly-linked list，并且是按数字的reverse order。要求输出这两个数的sum，使用与输入相同的表达方式。
Constraints:
- The number of nodes in each linked list is in the range [1,100]. 即没有空list。
- 0 <= Node.val <= 9 （每位都是0到9，没有字母）
- It is guaranteed that the list represents a number that does not have leading zeros. （没有leading zero，意味着list的最后的元素如果是0，那这个数字就是0，此时list的长度为1）
最大的数可能有100位digit，这是个超大的数字，远远超过了64位unsigned数字可以表达的范围。
>>> len(str(0xFFFFFFFF)) # length of max 32bits integer
10
>>> len(str(0xFFFFFFFFFFFFFFFF)) # length of max 64bits integer
20
这意味着，采用C/C++时，不能使用转int后作加法的思路。其实，reverse order已经简化了问题，个位在singly-linked list的最开始，可以直接开始按位做加法。non-negative也简化了问题，singly-linked list最后不会出现符号。
将输入的数字转成int，相加，再转回输出格式，这显然很低效，而且输入的数字可能有100位，C/C++方案肯定不能这么干。因此，自然而然的思路，就是从左到右按位做加法，无它。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
rtv = l3 = ListNode(0)
c = 0
while l1 or l2:
s = 0
if l1:
s += l1.val
l1 = l1.next
if l2:
s += l2.val
l2 = l2.next
s += c
c = s // 10
l3.next = l3 = ListNode(s%10)
if c == 1:
l3.next = ListNode(1)
return rtv.next
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode *rtv, *l3;
rtv = l3 = new ListNode{};
int s, c{};
while(l1 || l2){
s = 0;
if(l1){
s += l1->val;
l1 = l1->next;
}
if(l2){
s += l2->val;
l2 = l2->next;
}
s += c;
c = s / 10;
l3 = l3->next = new ListNode{s%10};
}
if(c)
l3 = l3->next = new ListNode{1};
ListNode *head {rtv};
rtv = rtv->next;
delete head;
return rtv;
}
};
new失败会raise，因此无需判断返回的指针。但如果真的发生new失败，这里不处理，就会memory leak。C++的Exception Safety分成4个level，这种不处理的情况处于最低level，叫做
No exception guarantee— If the function throws an exception, the program may not be in a valid state: resource leaks, memory corruption, or other invariant-destroying errors may have occurred. 最高level是那些被标记为noexcept的接口，保证不会throw。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2){
struct ListNode *rtv, *l3;
rtv = l3 = malloc(sizeof(struct ListNode));
int s, c=0;
while(l1 || l2){
s = 0;
if(l1){
s += l1->val;
l1 = l1->next;
}
if(l2){
s += l2->val;
l2 = l2->next;
}
s += c;
l3 = l3->next = malloc(sizeof(struct ListNode));
l3->val = s % 10;
c = s / 10;
}
if(c){
l3 = l3->next = malloc(sizeof(struct ListNode));
l3->val = 1;
}
l3->next = NULL;
struct ListNode *head;
head = rtv;
rtv = rtv->next;
free(head);
return rtv;
}
void*隐式地转换成其它类型的指针，因此以上代码不需要强转malloc的返回。但C++不允许！class Solution:
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
t = l1
s1 = ''
while t:
s1 += str(t.val)
t = t.next
t = l2
s2 = ''
while t:
s2 += str(t.val)
t = t.next
s = str(int(s1[::-1])+int(s2[::-1]))[::-1]
h = t = ListNode(int(s[0]))
for c in s[1:]:
t.next = ListNode(int(c))
t = t.next
return h
本文链接：https://cs.pynote.net/ag/leetcode/202203171/
-- EOF --
-- MORE --