给定一个用单链表表示的整数,然后把这个整数加一。
数据范围:链表长度满足 ,链表上每个节点的值满足 ,可以保证链表在非 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; } }
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; } }
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; } }
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; }
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} }
思路:链表反转,进位加法。初始进位位为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; } }
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; } }
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; }
// 递归法求解 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; } } };
/** * 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; } };
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; }
/** * 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; } } };
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; } }
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; };
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; }
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; } }
在原链表上加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; } }
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