给单链表加一

题意

给一个用链表表示的数字，对它加1，并返回加法后的链表

方法

递归

分析

真实的加一操作仅仅发生在末位

剩下的位上如果数字要变，都是因为进位

因此分成两部分

1. 递归找到最低位加一
2. 如果当前值等于10，则进位到它的父节点

因此，递归过程传递当前节点和它的父节点

对于根部需要特殊处理，也就是

1. 根节点的父节点是NULL
2. 如果根节点+1后为10，还需要额外增加节点

代码

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    ListNode* add1(ListNode* node,ListNode * parent){ // 节点和它的 父节点
        if(!node -> next){ // 最后一个节点直接加1
            node -> val ++;
        }else{
            add1(node->next, node); // 非最后一个递归向下
        }
        if(node -> val == 10){ // 进位
            node -> val = 0;
            if(parent){ // 有父节点
                parent -> val ++;
            }else{ // 根 无父节点
                parent = new ListNode(1);
                parent->next = node;
            }
        }
        return parent?parent:node; // 根是否进位
    }
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    ListNode* plusOne(ListNode* head) {
        return add1(head, NULL);
    }
};

复杂度分析

空间复杂度: 主要和递归深度相关，空间复杂度为$O(n)O(n)$

时间复杂度: 每个节点操作代价为常数代价，所以总时间复杂度为$O(n)O(n)$

转换成数字再转换成链表

分析

有不少实际应用中，虽然传递的是引用，但是并不希望你对内容的更改

需要完全新生成链表

这种情况，不如直接把原始链表转换成数字，加一以后，再转换回链表

返回新的链表，就是要求的结果

样例

以样例数据为例

代码

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param head ListNode类 
# @return ListNode类
#
class Solution:
    def plusOne(self , head: ListNode) -> ListNode:
        v = 0
        p = head
        while p: # 转换成数字
            v *= 10
            v += p.val
            p = p.next
        v += 1 # 加一
        # 数字再转换成链表
        r = None
        while v:
            n = ListNode(v%10) # 新节点
            n.next = r # 指向低位
            r = n
            v //=10
        return r

复杂度分析

空间复杂度: 主要消耗在生成的链表上，空间复杂度为$O(n)O(n)$

时间复杂度: 对于每位，链表每个节点运算代价为常数，所以总时间复杂度为$O(n)O(n)$