给定一个用单链表表示的整数，然后把这个整数加一。
数据范围：链表长度满足 
，链表上每个节点的值满足 
，可以保证链表在非 0 的情况下没有前导零
例如输入{1,2,3}时，对应的输出为{1,2,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) {
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)
这个题可以看作是“链表反转”和“链表加法”两个题的结合：
- 先做一个链表的反转，让高位在头，低位在尾；
- 然后把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
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)
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)
public ListNode plusOne (ListNode head) {
// 入栈
Stack<ListNode> stack = new Stack<>();
while(head != null) {
stack.push(head);
head = head.next;
}
int addOne = 1;
ListNode result = null;
// 出栈，然后给出栈的元素加1，根据结果判断下次是否需要进位
// 最后就是相当于反转链表了
while(addOne != 0 || !stack.isEmpty()) {
int var = stack.isEmpty() ? 0 : stack.pop().val;
int sum = var + addOne;
addOne = sum >= 10 ? 1 : 0;
ListNode node = new ListNode(sum % 10);
node.next = result;
result = node;
}
return result;
}
发表于 2023-04-15 14:46:17
回复(0)
package main
import _"fmt"
import . "nc_tools"
/*
* type ListNode struct{
* Val int
* Next *ListNode
* }
*/
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param head ListNode类
* @return ListNode类
*/
func plusOne( head *ListNode ) *ListNode {
arr:=[]*ListNode{}
for p:=head;p!=nil;p=p.Next{
arr=append(arr,p)
}
carry:=1
for i:=len(arr)-1;i>=0;i--{
carry+=arr[i].Val
if carry!=10{
arr[i].Val=carry
return head
}else{
arr[i].Val=0
carry=1
}
}
return &ListNode{1,head}
}
发表于 2023-03-09 00:10:08
回复(0)
思路：链表反转，进位加法。初始进位位为1，特殊判题是只有一个节点的时候。时间复杂度O（n)
import java.util.*;
public class Solution {
public ListNode plusOne (ListNode head) {
if(head.next == null) {
if(head.val < 9) head.val += 1;
else {
head.val = 0;
head.next = new ListNode(1);
}
return reverse(head);
}
ListNode p = head;
p = head = reverse(head);
int nextAdd = 1;
ListNode pre = p;
while(p != null) {
int temp = p.val + nextAdd;
nextAdd = temp >= 10 ? 1 : 0;
temp = temp % 10;
p.val = temp;
pre = p;
p = p.next;
}
if(nextAdd == 1) {
pre.next = new ListNode(1);
}
return reverse(head);
}
public ListNode reverse(ListNode head) {
if(head == null || head.next == null) {
return head;
}
ListNode phead = reverse(head.next);
head.next.next = head;
head.next = null;
return phead;
}
}
发表于 2023-02-25 00:18:53
回复(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) {
// write code here
ListNode a=null,b=head;
for(;b!=null;){
ListNode c=b.next;
b.next=a;
a=b;
b=c;
}
b=a;
while(true){
if(a.val==9){
a.val=0;
}else{
a.val++;
break;
}
if(a.next!=null){
a=a.next;
}else{
a.next=new ListNode(1);
break;
}
}
a=null;
for(;b!=null;){
ListNode c=b.next;
b.next=a;
a=b;
b=c;
}
return a;
}
}
发表于 2023-01-25 12:33:25
回复(0)
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)
// 递归法求解
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param head ListNode类
* @return ListNode类
*/
bool carry = false;
void sum(ListNode* head) {
if (head->next != nullptr)
sum(head->next);
if (head->next == nullptr || carry) {
if (head->val == 9) {
head->val = 0;
carry = true;
} else {
head->val++;
carry = false;
}
}
}
ListNode* plusOne(ListNode* head) {
// write code here
sum(head);
if (head->val == 0 && carry) {
ListNode* newHead = new ListNode(1);
newHead->next = head;
carry = false;
return newHead;
} else {
return head;
}
}
};
发表于 2022-12-19 18:42:45
回复(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类
*/
int add=1;
public ListNode plusOne (ListNode head) {
if (head==null){
return null;
}
recursion(head);
if (add!=0){
ListNode newHead=new ListNode(add);
newHead.next=head;
head=newHead;
}
return head;
}
private void recursion(ListNode head) {
if (head==null){
return;
}
recursion(head.next);
int pre=head.val;
head.val= (pre+add)%10;
add= (pre+add)/10;
}
}
/*
* public class ListNode {
* int val;
* ListNode next = null;
* public ListNode(int val) {
* this.val = val;
* }
* }
*/
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param head ListNode类
* @return ListNode类
*/
int add=1;
public ListNode plusOne (ListNode head) {
if (head==null){
return null;
}
recursion(head);
if (add!=0){
ListNode newHead=new ListNode(add);
newHead.next=head;
head=newHead;
}
return head;
}
private void recursion(ListNode head) {
if (head==null){
return;
}
recursion(head.next);
int pre=head.val;
head.val= (pre+add)%10;
add= (pre+add)/10;
}
}
发表于 2022-10-29 16:30:21
回复(0)
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* ListNode(int x) : val(x), next(nullptr) {}
* };
*/
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param head ListNode类
* @return ListNode类
*/
ListNode* plusOne(ListNode* head) {
// write code here
if(head == NULL) return head;
ListNode* cur = head;
int k = 0;
int carry = 1;
// 找到最后一个位置 并且记录个数
while(cur != nullptr && cur->next != nullptr)
{
k++;
cur = cur -> next;
}
// 对最后一个数加1
int val = cur->val + carry;
cur ->val = val % 10;
carry = val / 10;
// 如果加完了 也就是 k 不存在了 或者 不要加了 就跳出
while(carry && k > 0)
{
cur = head;
for(int i=1; i<k; i++)
{
cur = cur->next;
}
int val = cur->val + carry;
cur ->val = val % 10;
carry = val / 10;
k--;
}
// 加完之后 发现 这个进位还是存在的
if(carry)
{
ListNode* node = new ListNode(carry);
node -> next = head;
head = node;
}
return head;
}
};
发表于 2022-08-25 10:05:19
回复(0)
ListNode* plusOne(ListNode* head) {
//if(!head)
ListNode* res = new ListNode(-1);
res->next = head;
rev(res);
int c = 1;
ListNode* now = res;
while (now->next) {
now->next->val += c;
c = now->next->val / 10;
now->next->val %= 10;
now = now->next;
}
if (c) {
now->next = new ListNode(c);
}
rev(res);
return res->next;
}
发表于 2022-08-15 12:25:36
回复(0)
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* ListNode(int x) : val(x), next(nullptr) {}
* };
*/
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param head ListNode类
* @return ListNode类
*/
ListNode* reverse(ListNode* root) {
ListNode* per = nullptr;
while (root) {
ListNode* next = root->next;
root->next = per;
per = root;
root = next;
}
return per;
}
//两次翻转方式
ListNode* plusOne(ListNode* head) {
head=this->reverse(head);
ListNode* root=head;
ListNode* per=nullptr;
bool tims=1;
int num=0;
while(root)
{
if(tims){
num = root->val + 1;
tims=false;
}
else num=root->val + num;
root->val = num % 10;
num/=10;
//不需要进位
if(!num)break;
per=root;
root=root->next;
}
if(num)per->next=new ListNode(num);
return this->reverse(head);
}
//递归方式
ListNode* plusOne1(ListNode* head) {
// write code here
ListNode* res = new ListNode(0);
res->next = head;
function<int(ListNode* )> fun = [&](ListNode * root)->int{
if (!root->next) {
int num = root->val + 1;
root->val = num % 10;
return num / 10;
}
int num = fun(root->next) + root->val;
root->val = num % 10;
return num / 10;
};
fun(res);
if (res->val)return res;
else {
ListNode* tmp = res->next;
delete res;
return tmp;
}
}
};
发表于 2022-08-12 19:39:07
回复(0)
思路：使用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)
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param head ListNode类
* @return ListNode类
*/
ListNode* plusOne(ListNode* head) {
// write code here
help(head);
if(res==1)
{
ListNode* tmp=new ListNode(1);
tmp->next=head;
return tmp;
}
return head;
}
void help(ListNode* head)
{
if(!head)
{
return;
}
help(head->next);
head->val+=res;
res=head->val/10;
head->val%=10;
}
private:
int res=1;
};
发表于 2022-06-22 17:09:41
回复(0)
叠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)
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)
在原链表上加1，需要向前进位，但单链表不能后退，所以先把链表反转，然后像两个链表相加求和(leetcode 2. 两数相加/)那样加一，最后再次反转链表就是答案。
直接在原链表上操作
import java.util.*;
public class Solution {
public ListNode plusOne (ListNode head) {
head = reverse(head);
int progress = 1;
ListNode cur = head;
while(progress == 1){
int num = cur.val + 1;
progress = num > 9 ? 1 : 0;
cur.val = num%10;
if(progress == 1 && cur.next == null){
cur.next = new ListNode(1);
break;
}
cur = cur.next;
}
return reverse(head);
}
public ListNode reverse(ListNode head){
ListNode pre = null;
while(head != null){
ListNode tmp = head.next;
head.next = pre;
pre = head;
head = tmp;
}
return pre;
}
} 创造新的链表。
import java.util.*;
public class Solution {
public ListNode plusOne (ListNode head) {
head = reverse(head);
int progress = 1;
ListNode dummy = new ListNode(0);
ListNode cur = dummy;
while(progress == 1 || head != null){
int num = head == null ? 0 : head.val;
num += progress;
progress = num > 9 ? 1 : 0;
ListNode node = new ListNode(num % 10);
cur.next = node;
cur = cur.next;
head = head == null ? null : head.next;
}
return reverse(dummy.next);
}
public ListNode reverse(ListNode head){
ListNode pre = null;
while(head != null){
ListNode tmp = head.next;
head.next = pre;
pre = head;
head = tmp;
}
return pre;
}
}
发表于 2022-01-09 17:36:55
回复(0)
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param head ListNode类
* @return ListNode类
*/
ListNode* plusOne(ListNode* head) {
// write code here
int cmp[10000];
ListNode *pMove=head;int n=0;
while(pMove)
{
cmp[n]=pMove->val;
pMove=pMove->next;
n++;
}
cmp[n-1]+=1;
if( cmp[n-1]==10)
{
int t=0;
for(int i=n-1;i>=0;i--)
{
t+=cmp[i];
cmp[i]=t%10;
t/=10;
}
if(cmp[0]==0)
{
for(int i=n;i>=1;i--)
{
cmp[i]=cmp[i-1];
}
cmp[0]=1;
ListNode* node=new ListNode(1);
node->next=head;
head=node;
}
pMove=head;n=0;
while(pMove)
{
pMove->val=cmp[n];
n++;
pMove=pMove->next;
}
return head;
}
n=0;
pMove=head;
while(pMove)
{
pMove->val=cmp[n];
n++;
pMove=pMove->next;
}
return head;
}
};
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param head ListNode类
* @return ListNode类
*/
ListNode* plusOne(ListNode* head) {
// write code here
int cmp[10000];
ListNode *pMove=head;int n=0;
while(pMove)
{
cmp[n]=pMove->val;
pMove=pMove->next;
n++;
}
cmp[n-1]+=1;
if( cmp[n-1]==10)
{
int t=0;
for(int i=n-1;i>=0;i--)
{
t+=cmp[i];
cmp[i]=t%10;
t/=10;
}
if(cmp[0]==0)
{
for(int i=n;i>=1;i--)
{
cmp[i]=cmp[i-1];
}
cmp[0]=1;
ListNode* node=new ListNode(1);
node->next=head;
head=node;
}
pMove=head;n=0;
while(pMove)
{
pMove->val=cmp[n];
n++;
pMove=pMove->next;
}
return head;
}
n=0;
pMove=head;
while(pMove)
{
pMove->val=cmp[n];
n++;
pMove=pMove->next;
}
return head;
}
};
发表于 2021-12-20 21:47:58
回复(0)
class Solution: def plusOne(self , head: ListNode) -> ListNode: # write code here a=[] while head: a.append(head) head=head.next is_add=True for i in range(len(a)): if is_add: val_new = a[-i-1].val+1 a[-i-1].val=val_new if val_new>=10: a[-i-1].val=val_new-10 else: head_new=a[0] break if i==len(a)-1: head_new=ListNode(1) head_new.next=a[0] return head_new
发表于 2021-11-23 00:08:17
回复(0)
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
