向整数数字的链表表示加一

Question

我正在努力解决这个挑战：

给定一个表示为非空单向链表的非负整数，给该整数加一。

您可以假设该整数不包含任何前导零，除了数字 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 并得到正确的答案。

Answer 1

当最后一位数字是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的节点）加一，并报告是否有剩余的进位必须应用于当前节点。 节点。

关于您的代码的一些其他注释：

• 在C++中你不应该使用

  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

 字段。提交之前，请确保使用它们的类型和字段。