首页 > 试题广场 >

给单链表加一

[编程题]给单链表加一
  • 热度指数：2568 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定一个用单链表表示的整数，然后把这个整数加一。

数据范围：链表长度满足 ，链表上每个节点的值满足 ，可以保证链表在非 0 的情况下没有前导零

例如输入{1,2,3}时，对应的输出为{1,2,4}，转换过程如下图所示：

示例1

输入

{1,2,3}

输出

{1,2,4}
示例2

输入

{1,2,0}

输出

{1,2,1}
示例3

输入

{9}

输出

{1,0}

说明：本题目包含复杂数据结构ListNode，点此查看相关信息
算法知识视频讲解
添加回答
Java
梁山教父头像 梁山教父 
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
        int size=0;
        ListNode tmp=head;
        //计算链表长度
        while(tmp!=null){
            size++;
            tmp=tmp.next;
        }
        //创建数组
        int arr[]=new int[size];
        int i=0;
        tmp=head;
        //将链表值放进数组
        while(tmp!=null){
            arr[i]=tmp.val;
            tmp=tmp.next;
            i++;
        }
        //如果为true需进位
        boolean add=true;
        //进行+1
        for(i=arr.length-1;i>=0;i--){
            //最后一位小于9直接+1返回
            if(arr[i]<9){
                arr[i]++;
                add=false;
                break;
            }else{
                //否则置为0，上一位进位
                arr[i]=0;
            }
        }
        //如果为进位标记，进行进位
        if(add==true){
            arr=new int[size+1];
            arr[0]=1;
        }
        //将数组值放置到链表
        ListNode tmpNode=new ListNode(arr[0]);
        ListNode returnList=tmpNode;
        for(i=1;i<arr.length;i++){
            ListNode node=new ListNode(arr[i]);
            tmpNode.next=node;
            tmpNode=tmpNode.next;
        }
        return returnList;
    }
}

发表于 2023-05-19 09:47:42 回复(0)
Java
腰马合一小垃圾头像 腰马合一小垃圾 
public ListNode plusOne (ListNode head) {
        if(head == null){
            return head;
        }
        // write code here
        ListNode dummy = new ListNode(-1);
        dummy.next = reverse(head);
        ListNode cur = dummy.next;
        int carry = (cur.val + 1) / 10;
        cur.val = (cur.val + 1) % 10;
        cur = cur.next;
        while(cur != null && carry > 0){
            int sum = cur.val + carry;
            cur.val = sum % 10;
            carry = sum / 10;
            cur = cur.next;
        }
        if(carry > 0){
            ListNode newHead = new ListNode(carry);
            newHead.next = dummy.next;
            return newHead;
        }
        return reverse(dummy.next);
    }

    private ListNode reverse(ListNode head){
        ListNode pre = null;
        ListNode next = null;
        while(head != null){
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }

发表于 2023-01-07 20:48:41 回复(0)
Java
雷欧尼桑头像 雷欧尼桑
思路：使用nineNode记录链表中最后一个值不为9的节点，然后将nineNode的值自增1，后面的都赋值为0。 
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) {
        ListNode notNineNode = null;
        ListNode pre = new ListNode(0);
        pre.next = head;
        ListNode node = pre;
        while (node != null) {
            if (node.val != 9) {
                notNineNode = node; 
            }
            node = node.next;
        }
        if (notNineNode != null) {
            notNineNode.val++;
            notNineNode = notNineNode.next;
        }
        while (notNineNode != null) {
            notNineNode.val = 0;
            notNineNode = notNineNode.next;
        }
        return pre.val != 0 ? pre : pre.next;
    }
}
发表于 2022-07-17 21:18:13 回复(0)
Java
blue&&lan头像 blue&&lan
叠buff代码 
static boolean f=true,r=true,s=true;
static ListNode pre=null;
    public ListNode plusOne (ListNode head) {
        if(r){
            pre=head;
            pre.val+=1;
            r=false;
        }
        if(head==null){
            return head;
        }
        ListNode node=plusOne(head.next);
        ListNode p=node;
        if(p==null&&head.val>9){
            ListNode pp=new ListNode(1);
            head.val=0;
            head.next=p;
            pp.next=head;
            return pp;
        }
        else if(p==null){
            head.next=p;
            return head;
        }
        if(p.val!=9&&f){
            p.val+=1;
            f=false;
        }else if(p.val==9&&f){
            p.val=0;
        }
        if(!f&&s){
            pre.val-=1;
            s=false;
        }else if(f&&s&&head.val>9){
            ListNode pp=new ListNode(1);
            head.val=0;
            head.next=p;
            pp.next=head;
            return pp;
        }
        head.next=p;
        return head;
    }


发表于 2022-06-08 17:55:44 回复(0)
Java
老农爱编程头像 老农爱编程 
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
        //创建一个集合去存放元素
        List<Integer> list = new ArrayList<Integer>();
        while(head != null){
            list.add(head.val);
            head = head.next;
        }
        ListNode tail = null;//尾结点
        int flag = 0 ; //进位
        int i = list.size() - 1;
        while(i >= 0){
            if(i == list.size() - 1){
                int val = list.get(i) + 1 >= 10 ? 0 : list.get(i) + 1;
                flag = list.get(i) + 1 >= 10 ? 1 : 0;
                //同时封装成节点并且进行链表的反转
                ListNode temp = new ListNode(val);
                temp.next = tail;
                tail = temp;
            }else{
                int val = list.get(i) + flag >= 10 ? 0 : list.get(i) + flag;
                flag = list.get(i) + flag >= 10 ? 1 : 0;
                //同时封装成节点并且进行链表的反转
                ListNode temp = new ListNode(val);
                temp.next = tail;
                tail = temp;
            }
            i -- ;
            
        }
        //循环结束后如果还有进位1
        if(flag == 1){
            ListNode l = new ListNode(1);
            l.next = tail;
            tail = l;
        }
        return tail;
    }
}

发表于 2022-03-17 21:59:57 回复(0)
Java
FARO_Z头像 FARO_Z

反转以后再做加法

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) {
        if (head==null) return new ListNode(1);
        head = reverse(head);
        ListNode curr = head;
        ListNode pre=null;
        int cache = 1;
        while (curr!=null) {
            int val = curr.val + cache;
            curr.val=val%10;
            cache=val/10;
            pre=curr;
            curr=curr.next;
        }
        if (cache!=0) pre.next=new ListNode(cache);
        return reverse(head);
    }

    public ListNode reverse(ListNode head) {
        if (head==null || head.next==null) return head;
        ListNode pre = null;
        ListNode curr = head;
        while (curr!=null) {
            ListNode tmp = curr.next;
            curr.next=pre;
            pre=curr;
            curr=tmp;
        }
        return pre;
    }
}
发表于 2022-01-18 11:46:00 回复(0)
Java
pein531头像 pein531
这个题可以看作是“链表反转”和“链表加法”两个题的结合：
  1. 先做一个链表的反转，让高位在头，低位在尾；
  2. 然后把1这个数字转化成一个只有一个节点的链表；
  3. 将以上两个链表模拟竖式加法，做一个链表两数之和；
  4. 最后把两数之和的链表反转过来返回。 
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
        head = reverseList(head);
        ListNode anotherHead = new ListNode(1);
        return reverseList(addTwoNumbers(head, anotherHead));
    }
    
    private ListNode addTwoNumbers(ListNode num1, ListNode num2) {
        ListNode p1 = num1, p2 = num2;
        int carry = 0;
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;
        while(p1 != null || p2 != null){
            int sum = carry + (p1 != null? p1.val: 0) + (p2 != null? p2.val: 0);
            cur.next = new ListNode(sum % 10);
            carry = sum / 10;
            if(p1 != null) p1 = p1.next;
            if(p2 != null) p2 = p2.next;
            cur = cur.next;
        }
        if(carry > 0) cur.next = new ListNode(carry);
        return dummy.next;
    }
    
    private ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode cur = head;
        while(cur != null){
            ListNode next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }
}

发表于 2021-12-13 09:30:17 回复(1)
提交观点

问题信息

模拟 链表
难度：
7条回答 1854浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号