题目描述

一个单向链表表示一个非负整数，整数高位靠链表头。比如123: 1->2->3，对这个链表表示的整数加1，返回加1操作后的链表表示的整数

样例

input:
1->2->3

output:
1->2->4

算法1

递归

从尾到头遍历链表，因为链表是单向的，访问当前结点的前一个结点需要从前到后遍历，复杂度为O(n)，因此使用递归在O(1)时间内实现访问当前结点的前一个结点（这里也可以手工维护一个栈）。每次递归返回当前结点在对链表加1操作后是否有进位。

时间复杂度分析：每个结点访问一次 O(n)

Java 代码

class Solution {
    public ListNode plusOne(ListNode head) {
        int add = dfs(head);
        if(add>0) {
            ListNode node = new ListNode(add);
            node.next = head;
            return node;
        }else return head;
    }

    private int dfs(ListNode node) {
        if(node==null) return 1;
        int add=dfs(node.next);
        if(add>0) node.val++;
        if(node.val>9) {
            node.val-=10;
            return 1;
        }else return 0;
    }
}