我正在努力解决这个挑战:
给定一个表示为非空单向链表的非负整数,给该整数加一。
您可以假设该整数不包含任何前导零,除了数字 0 本身。
存储数字时,最高有效数字位于列表的开头。
示例:
输入:1->2->3
输出:1->2->4
这是我的代码:
class Solution
{
public:
Node* addOne(Node *head)
{
if (head == NULL)
{
return head;
}
Node* Temp = head;
while (Temp->next != NULL)
{
Temp=Temp->next;
}
Temp->data = Temp->data+1;
return head;
}
};
我在 LeetCode 上提交了该代码,但它给了我一个错误,并且无法通过所有测试用例。
我的代码将最后一个节点的值增加 1,但是当该值是 9 时,结果是错误的。我不知道如何将该数据变成 0 并得到正确的答案。
当最后一位数字是9时,必须应用小学教的方法:将该数字设为0,并传递进位1与前一位数字相加。如果前一个数字也是 9,则对其前面的数字重复此过程。在最终的情况下,所有数字恰好都是 9,将它们全部更新为 0 后,您需要在列表前添加一个值为 1(进位)的新节点。
输入和预期输出的一些示例:
输入 | 预期产出 |
---|---|
1→2→3 | 1→2→4 |
1→2→9 | 1→3→0 |
1→9→9 | 2→0→0 |
9→9→9 | 1→0→0→0 |
在您的方法中,您丢失了对前一个数字的引用,因此您无法轻松返回节点以在那里应用进位。您可以通过不同的方式解决这个问题。一种是编写一个递归函数,它将向列表的remainder(即当前节点after的节点)加一,并报告是否有剩余的进位必须应用于当前节点。 节点。
关于您的代码的一些其他注释:
NULL
,而应该使用
nullptr
。您通常甚至可以省略它,而只测试节点引用的真实性。
Temp
) 开头,而应使用驼峰命名法。 PascalCase(首字母大写)通常用于类和接口的名称,但不适用于局部变量。
class Solution
{
bool addOneAndGetCarry(Node *head) {
if (!head) {
// At the end of the list we return a carry
return true;
}
if (!addOneAndGetCarry(head->next)) {
// If there is no carry we're done
return false;
}
// Add the carry
head->data = (head->data + 1) % 10;
// Determine if we need to cascade a carry
std::cout << "return " << (head->data == 0) << "\n";
return head->data == 0;
}
public:
Node* addOne(Node *head) {
if (addOneAndGetCarry(head)) {
// We have a carry: prefix digits with a new digit
head = new Node(1, head);
}
return head;
}
};
在最后一个节点上:LeetCode 问题 369 使用 NodeList
作为类型而不是
Node
,并且具有
val
字段而不是
data
字段。提交之前,请确保使用它们的类型和字段。