X

LEETCODE 369. Plus One Linked List 解题思路分析

题目大意:

给单链表加一

用一个 非空 单链表来表示一个非负整数,然后将这个整数加一。

你可以假设这个整数除了 0 本身,没有任何前导的 0。

这个整数的各个数位按照 高位在链表头部、低位在链表尾部 的顺序排列。

示例:

输入: [1,2,3]
输出: [1,2,4]

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=369

解题思路分析:

遇到链表题肯定要用上递归思路,利用本题给出的head节点,一路递归到最未节点,先将其val加一,如果val小于10,直接将加一后的数值保存至节点。如果val等于10,这时出现进位,当前节点值为0,进位1,我们将进位作为返回值返回给上一层递归函数。在上层递归函数中,我们先查看下层递归函数的返回值(进位),将其累加到自身,如果等于10,依然需要进位,继续返回1给更上层的递归函数。

注意一点,当递归结束时,进位依然是1,那么我们需要新建一个头结点,将其赋值为1,然后再将原先的头结点加入到其后方即可。比如输入[9, 9],加一后的输出应该是[1, 0, 0]。

public ListNode plusOne(ListNode head) {
    int carry=help(head); // 递归求解
    if(carry==0) return head; // 如果进位为0,直接返回head
    // 如果进位为1,新建一个头结点
    ListNode node = new ListNode(1);
    // 将原先的头结点连接到新建节点后方
    node.next=head;
    return node;
}
// 递归函数,返回值为进位数
int help(ListNode head){
    // 如果头为空,返回0
    if(head==null) return 0;
    // 当前节点值
    int val=head.val;
    // 如果当前节点为末尾结点,值加一
    if(head.next==null) val+=1;
    // 递归取得后一节点的进位数
    int carry=help(head.next);
    // 当前节点的值加上进位数
    val += carry;
    // 如果当前节点值为10,需要进位
    if(val==10){
        // 当前值为0
        head.val = 0;
        // 进位1
        return 1;
    }else{
        // 当前值不变
        head.val = val;
        // 进位0
        return 0;
    }
}

本题解法执行时间为0ms。

Runtime: 0 ms, faster than 100.00% of Java online submissions for Plus One Linked List.

Memory Usage: 34.5 MB, less than 100.00% of Java online submissions for Plus One Linked List.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: https://leetcode.jp/leetcode-369-plus-one-linked-list-解题思路分析/
Categories: leetcode
kwantong: