链表表示的整数加1问题：现有C++代码无法通过LeetCode测试

你的代码只处理了最后一位直接加1的简单场景，没考虑进位情况——比如输入9->9时，预期输出是1->0->0，但你的代码会输出9->10，这显然不符合要求。下面给两种可行的解决方案：

方法一：反转链表处理进位 #

思路是先把链表反转，让低位（原链表末尾）变成头部，这样就能从低位开始处理加1和进位，最后再反转回来得到结果：

class Solution {
private:
    Node* reverseList(Node* head) {
        Node* prev = nullptr;
        Node* curr = head;
        while (curr != nullptr) {
            Node* nextTemp = curr->next;
            curr->next = prev;
            prev = curr;
            curr = nextTemp;
        }
        return prev;
    }
public:
    Node* addOne(Node *head) {
        if (head == nullptr) return head;
        
        // 反转链表，让原末尾的低位到头部
        Node* reversedHead = reverseList(head);
        Node* curr = reversedHead;
        int carry = 1; // 初始进位为1，因为要加1
        
        while (curr != nullptr && carry > 0) {
            int sum = curr->data + carry;
            curr->data = sum % 10;
            carry = sum / 10;
            
            // 如果还有进位且到了链表末尾，新增一个节点
            if (carry > 0 && curr->next == nullptr) {
                curr->next = new Node(1);
                carry = 0;
            }
            curr = curr->next;
        }
        
        // 再次反转，恢复原顺序得到结果
        return reverseList(reversedHead);
    }
};

方法二：定位最后一个非9节点 #

这种方法不需要反转链表，直接找到链表中最后一个值不是9的节点：

1. 如果找到这样的节点，把它的值加1，然后将它后面所有的9都改成0
2. 如果所有节点都是9（比如9->9->9），就新建一个值为1的头节点，把原来的所有节点改成0接在后面

class Solution {
public:
    Node* addOne(Node *head) {
        if (head == nullptr) return head;
        
        Node* lastNonNine = nullptr;
        Node* curr = head;
        
        // 遍历找到最后一个不是9的节点
        while (curr != nullptr) {
            if (curr->data != 9) {
                lastNonNine = curr;
            }
            curr = curr->next;
        }
        
        if (lastNonNine != nullptr) {
            // 非9节点加1
            lastNonNine->data += 1;
            // 后面的所有9改成0
            curr = lastNonNine->next;
            while (curr != nullptr) {
                curr->data = 0;
                curr = curr->next;
            }
            return head;
        } else {
            // 所有节点都是9，新建头节点1
            Node* newHead = new Node(1);
            newHead->next = head;
            // 原所有节点改为0
            curr = head;
            while (curr != nullptr) {
                curr->data = 0;
                curr = curr->next;
            }
            return newHead;
        }
    }
};

两种方法的时间复杂度都是O(n)，空间复杂度都是O(1)（除了可能新增的一个节点）。方法二更高效一些，因为只需要最多两次遍历，不需要反转链表的额外操作。

内容的提问来源于stack exchange，提问作者Ashu Banna