​LeetCode刷题实战369:给单链表加一

共 3457字,需浏览 7分钟

 ·

2021-09-02 16:58

算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !

今天和大家聊的问题叫做 给单链表加一,我们先来看题面:
https://leetcode-cn.com/problems/plus-one-linked-list/

Given a non-negative integer represented as non-empty a singly linked list of digits, plus one to the integer.


You may assume the integer do not contain any leading zero, except the number 0 itself.


The digits are stored such that the most significant digit is at the head of the list.

用一个 非空 单链表来表示一个非负整数,然后将这个整数加一。
你可以假设这个整数除了 0 本身,没有任何前导的 0。
这个整数的各个数位按照 高位在链表头部、低位在链表尾部 的顺序排列。

示例


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


解题



这是一道linked list题,有几种情况需要考虑,
第一种情况正常,末尾不为9的时候直接+1
第二种情况,末尾为9的时候要向前进位置,还要判断如果全为9的话要新建一个链表头


/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode(int x) { val = x; }
 * }
 */

class Solution {
    public ListNode plusOne(ListNode head) {
        ListNode newHead = new ListNode(0);
        newHead.next = head;
        ListNode curr = newHead;
        ListNode curr_head = newHead;
        while(curr.next!=null){
            curr = curr.next;
            if(curr.val != 9){
                curr_head = curr;
            }
        }
        if(curr_head == curr){
            curr.val++;
        }else{
            curr_head.val++;
            curr = curr_head;
            while(curr.next != null){
                curr = curr.next;
                curr.val = 0;
            }
        }
        if(newHead.val == 0){
            newHead.next = null;
            return head;
        }else{
            return newHead;
        }
        
    }
}


好了,今天的文章就到这里,如果觉得有所收获,请顺手点个在看或者转发吧,你们的支持是我最大的动力 。

上期推文:

LeetCode1-360题汇总,希望对你有点帮助!
LeetCode刷题实战361:轰炸敌人
LeetCode刷题实战362:敲击计数器
LeetCode刷题实战363:矩形区域不超过 K 的最大数值和
LeetCode刷题实战364:加权嵌套序列和 II
LeetCode刷题实战365:水壶问题
LeetCode刷题实战366:寻找二叉树的叶子节点
LeetCode刷题实战367:有效的完全平方数
LeetCode刷题实战368:最大整除子集数

浏览 25
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐