题解 | # 给单链表加一

给单链表加一

http://www.nowcoder.com/practice/a2f1105d2ac5466e9ba8fd61310ba6d1

我觉得可以使用递归的方式来解决该题: 当链表数量大于1时:

  1. 添加一个值为0的新头节点,新头节点的next为head
  2. 递归计算next节点作为链表起点+1的值
  3. 计算完成后,如果next节点的值等于10,当前节点+1
  4. 判断头结点是否等于0。如果等于0说明没有超出原来的节点超度,返回head;如果大于0说明超出了原有的节点长度返回新头节点。

时间复杂度:O(n) 空间复杂度:O(1)

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    public ListNode plusOne (ListNode head) {
        // write code here
        ListNode newHead = new ListNode(0);
        newHead.next = head;
        plusOne2(newHead);
        return newHead.val==0?head:newHead;
    }
    
    public ListNode plusOne2 (ListNode curr) {
        // write code here
        if(curr.next == null){
            curr.val+=1;
            return curr;
        }
        ListNode next = plusOne2(curr.next);
        if(next.val==10) {
            next.val = 0;
            curr.val += 1;
        }
        return curr;
    }
}
全部评论
递归不累计空间复杂度,算时间复杂度
点赞 回复 分享
发布于 2022-04-18 22:18
空间复杂度为O(1)?函数递归调用不用栈的?
点赞 回复 分享
发布于 2022-04-18 21:58

相关推荐

不愿透露姓名的神秘牛友
07-03 18:22
投了几百份简历,专业和方向完全对口,都已读不回。尝试改了一下学校,果然有奇效。
steelhead:这不是很正常嘛,BOSS好的是即便是你学院本可能都会和聊几句,牛客上学院本机会很少了
点赞 评论 收藏
分享
机械打工仔:我来告诉你原因,是因为sobb有在线简历,有些HR为了快会直接先看在线简历,初步感觉不合适就不会找你要详细的了
投了多少份简历才上岸
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务