将一个以链表表示的数字加1

1. 题目描述

给定一个非空链表，每个节点表示其中的一个数字，在该链表代表的数字基础上加1，返回一个新的链表。

2. 思路分析

2.1 问题拆解

我们可以将问题拆解为以下几个部分：

1. 将链表逆序，方便从低位向高位增加；

2. 在链表的第一个元素上加1；

3. 处理进位情况；

4. 将链表再次逆序，得到最终结果。

2.2 代码实现

/**

 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* plusOne(ListNode* head) {
        //1. 将链表逆序
        head = reverseList(head);
        ListNode* p = head;
        int carry = 1; //进位
        while(p != NULL && carry != 0) { //循环处理进位情况，直到carry为0
            int sum = p->val + carry;
            carry = sum / 10;
            p->val = sum % 10;
            if(p->next == NULL && carry != 0) { //如果最后一位还有进位，需要新建节点
                p->next = new ListNode(0);
            }
            p = p->next;
        }
        //3. 将链表再次逆序
        head = reverseList(head);
        return head;
    }
    
private:
    ListNode* reverseList(ListNode* head) {
        if(head == NULL || head->next == NULL) {
            return head;
        }
        ListNode* newHead = reverseList(head->next);
        head->next->next = head;
        head->next = NULL;
        return newHead;
    }
};

3. 时间复杂度分析

链表中的每个元素只会被遍历一遍，因此时间复杂度为O(n)。

4. 注意事项

在处理进位情况时，需要注意链表的最后一位是否还有进位。如果存在进位，则需要新增一个节点。