题解 | #给单链表加一#

给单链表加一

题目描述 给定两个用字符串表示的二进制数，返回他们的和。

方法一：递归的方法

解题思路

对于本题，采用递归的方法进行求解，首先递归找到最低位加一，如果当前值等于10，则进位到它的父节点。对于根部需要特别注意，根节点的父节点设置成NULL，如果根节点进位，则还需要额外增加节点。

解题代码

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; // 根是否进位
    }
    ListNode* plusOne(ListNode* head)
    {
        return add1(head, NULL);
    }
};

复杂度分析

时间复杂度：使用递归，每个节点的操作代价为常数代价，因此时间复杂度为$O(n)O(n)$。

空间复杂度：使用递归，和递归深度有关，因此空间复杂度为$O(n)O(n)$。

方法二：转换的方法

解题思路

对于本题目的求解，还可以把原始链表转换成数字，加一以后，再转换回链表。

解题代码

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)$。