我正在尝试解决这个问题 leetcode 问题 C 语言,这是我想出的代码:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
#include <math.h>
struct ListNode *addTwoNumbers(struct ListNode *l1, struct ListNode *l2) {
struct ListNode *temp;
struct ListNode *sum = NULL;
int num1 = 0;
int num2 = 0;
temp = l1;
int n = 0;
int i = 0;
while (temp != NULL) {
num1 = num1 + (temp->val * pow(10, i));
i++;
temp = temp->next;
}
temp = l2;
i = 0;
while (temp != NULL) {
num2 = num2 + (temp->val * pow(10, i));
i++;
temp = temp->next;
}
int add = num1 + num2;
int tem = add;
i = 0;
for (i = 0; tem > 0; i++) {
tem = tem / 10;
}
if (add == 0) {
struct ListNode *new = malloc(sizeof(struct ListNode));
new->val = 0;
new->next = sum;
sum = new;
}
while (add > 0 && i > 0) {
struct ListNode *new = malloc(sizeof(struct ListNode));
new->val = add / pow(10, (i - 1));
new->next = sum;
i--;
add = add % (int)(pow(10, i));
sum = new;
}
return sum;
}
我不明白为什么测试用例 l1 = [9]; 的输出为空 l2 = [1,9,9,9,9,9,9,9,9,9]。它在许多测试用例中都是正确的,但问题似乎出在 add 是 10 的倍数(可能)的测试用例中。
您的方法是不够的:列表可能表示超出类型
int
或所有可用整数类型范围的数字,因为列表被指定为最多具有 100 个节点。对于长度超过 9 或 10 个节点的列表,将列表转换为其表示的数字将产生未定义的行为。使用pow
等浮点函数来执行整数计算通常是不合适的并且容易出错。
您应该为每个数字分配一个节点的新列表,其中包含参数列表的相应数字的总和,减少模 10 并将进位传播到下一个节点。
当到达其中一个列表的末尾时,继续传播另一个列表的进位,并在到达该列表的末尾时停止,分配一个额外的进位节点仍然不为零。
请注意,问题陈述并未指定您应该分配一个新列表,并且由于参数未指定为
const struct ListNode *
,因此您可以决定修改其中一个列表并返回指向其头节点的指针。通过将其中一个参数指定为 const
而不是另一个参数,可以使这一点更加明确。
这是一个简单的解决方案:
struct ListNode {
int val;
struct ListNode *next;
};
struct ListNode *addTwoNumbers(struct ListNode *l1, struct ListNode *l2) {
struct ListNode *head = NULL;
struct ListNode *tail = NULL;
int carry = 0;
while (l1 || l2 || carry) {
struct ListNode *node = malloc(sizeof(*node));
if (node == NULL) {
/* allocation error: free partially allocated number and
* return NULL.
*/
while (head) {
node = head;
head = head->next;
free(node);
}
break;
}
node->next = NULL;
/* compute the value of the sum digit and update the carry */
int digit = carry;
if (l1) {
digit += l1->val;
l1 = l1->next;
}
if (l2) {
digit += l2->val;
l2 = l2->next;
}
node->val = digit % 10;
carry = digit / 10;
/* append the node */
if (head == NULL) {
head = node;
} else {
tail->next = node;
}
tail = node;
}
return head;
}
如果你看一下清单,然后一一浏览会更容易,不需要用电源等让它变得复杂。就像用纸和铅笔做的那样。
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode* result = nullptr;
ListNode* last = nullptr;
int val{0};
int carry{0};
while (l1 || l2)
{
val = carry;
if (l1) val += l1->val;
if (l2) val += l2->val;
carry = 0;
if (val > 9)
{
carry = 1;
val -= 10;
}
auto* r = new ListNode(val);
if (result == nullptr)
{
result = last = r;
}
else
{
last->next = r;
last = r;
}
if (l1) l1 = l1->next;
if (l2) l2 = l2->next;
}
if (carry)
{
last->next = new ListNode(m_carry);
}
return result;
}
使用
ListNode
的要点是支持任意大的值。当您将值存储在 int num1
和 int num2
中时,整个目的就失败了,因为它仅限于 INT_MAX
,在我的系统上是 2147483647
(10 位数字)并且大于 num2
。有符号溢出是未定义的行为。
由于每个数字包含的信息少于 4 位,因此我为每个
unsigned char
使用了 int
(1 字节)而不是 ListNode::val
(在我的系统上为 4 字节)。
(未修复)
createDigit()
可以依赖调用者来初始化 next
。在这种情况下,createNumber()
和addTwoNumbers()
会在返回之前执行tail->next = NULL
。这会更快但不太安全。
(不固定)
free()
两个参数以及 addTwoNumbers()
中 main()
的返回值。
#include <stdio.h>
#include <stdlib.h>
// head of list is the least significant digit
struct ListNode {
unsigned char val;
struct ListNode *next;
};
struct ListNode *createDigit(struct ListNode *prev, unsigned char val) {
struct ListNode *newNode = malloc(sizeof *newNode);
if(!newNode) {
fprintf(stderr, "malloc failed\n");
return NULL;
}
newNode->val = val;
newNode->next = NULL;
if(prev) prev->next = newNode;
return newNode;
}
struct ListNode *createNumber(size_t n, const unsigned char vals[n]) {
if(!n) return NULL;
struct ListNode *head = NULL;
for(struct ListNode *tail = NULL; size_t i = 0; i < n; i++) {
tail = createDigit(tail, vals[i]);
if(!head) head = tail;
}
return head;
}
void printNumber(const struct ListNode *n) {
for(; n; n = n->next)
printf("%d", n->val);
printf("\n");
}
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
struct ListNode *head = NULL;
unsigned char carry = 0;
for(struct ListNode *tail = NULL; l1 || l2 || carry; l1 = l1 ? l1->next : NULL, l2 = l2 ? l2->next : NULL) {
unsigned char sum = (l1 ? l1->val : 0) +
(l2 ? l2->val : 0) +
carry;
tail = createDigit(tail, sum % 10);
if(!head) head = tail;
carry = sum / 10;
}
return head;
}
int main(void) {
printNumber(
addTwoNumbers(
createNumber(1, (unsigned char []) {9}),
createNumber(10, (unsigned char []) {1,9,9,9,9,9,9,9,9,9})
)
);
}
和示例输出:
00000000001