本文关键词：Leetcode, 力扣，链表相加，两数相加，两数之和，求加法，代码模板，Python, C++, Java
题目地址：https://leetcode-cn.com/problems/plus-one-linked-list/
题目描述
用一个非空 单链表来表示一个非负整数，然后将这个整数加一。
你可以假设这个整数除了 0 本身，没有任何前导的 0。
这个整数的各个数位按照 高位在链表头部、低位在链表尾部 的顺序排列。
示例:
输入: [1,2,3]
输出: [1,2,4]
题目大意
把一个用链表表示的整数加一，仍然用链表形式返回。
解题方法
前言
加法是我们上小学的时候开始学习的第一种数学运算。
在算法题中，「求加法」问题大多考察「列竖式」求和。
题目中，「两数之和」通常与其他形式表示的数字结合起来：
- 两个字符串形式的数字相加（第 415 题）
- 两个链表形式的数字相加（第 2 、445、369 题）
- 数组形式的数字相加（第 66 、989题）
- 两个二进制形式的数字相加（第 67 题）
做法都是非常类似的，本质是在考察各种数据表示形式：字符串，链表，数组，二进制。
我们只要掌握了用「列竖式」求「两数之和」的方法，这类题目全都可以秒杀。
十进制加法
我们先回顾一下十进制加法的计算过程：
使用「竖式」计算十进制的加法的方式：
1、 两个「加数」的右端对齐；
2、 从最右侧开始，从右向左依次计算对应的两位数字的和，如果有进位需要加上进位如果和大于等于10，则把和的个位数字计入结果，并向前面进位；
3、 重复步骤2；
4、 当两个「加数」的每个位置都计算完成，如果最后仍有进位，需要把进位数字保留到计算结果中；
在实现中需要注意的有：
1、 不可以把链表/字符串表示的「加数」先转化成int型数字再求和，因为可能溢出；
2、 两个「加数」的字符串长度可能不同；
3、 在最后，如果进位carry不为0，那么最后需要计算进位；
4、 注意结果数字是否为低位结果在前，根据题目要求判断最后是否要反转结果；
思路
本题与445. 两数相加 IIopen in new window 非常类似。只需要略微修改即可。
本题中给出的链表表示的数字是个位在后，高位在前。
因为加法需要从个位数开始相加，而链表的遍历是从头部（十进制的高位）开始的，因此我们需要把链表翻转过来。
那么就有了两种思路：
思路一：反转链表。****思路二：使用栈保存链表中的数字。（栈是先进后出的，所以起到了翻转功能）
我是用的方法是：不修改输入的链表，用思路二「栈」来解决。
方法：栈 + 循环
步骤：
1、 先把题目给出的链表遍历放到栈中；
2、 从栈中弹出栈顶数字digit，计算adder之和（adder在初始化的时候是1，之后都是0；表示链表与1相加），再加上进位carry，得到当前位置的和sum；
1、 如果sum>=10，那么进位carry=1，当前位设置为sum-10；
2、 如果sum<10，那么进位carry=0，当前位设置为sum；
3、 设置新链表节点，其值为sum，逆序拼接成链表即可；
代码中的巧妙之处：
1、 while(!st.empty()||adder!=0||carry>0)含义：
1、 栈中的元素没遍历完，或者adder不为0，那么就继续遍历；
2、 如果栈遍历完了，但是最后留下的进位carry!=0，那么需要把进位也保留到结果中；
2、 取栈顶元素的时候，如果栈已经遍历完了（即st.empty()），则认为当前的加数是0；
3、 逆序拼接链表的方法：先定义了一个哑结点dummy，然后每次把新构建的链表结点放到dummy和dummy->next之间，最后返回结果是dummy->next；
Java 语言的代码如下：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode plusOne(ListNode head) {
Stack<Integer> st = new Stack();
while (head != null) {
st.push(head.val);
head = head.next;
}
int carry = 0;
ListNode dummy = new ListNode(0);
int adder = 1;
while (!st.empty() || adder != 0 || carry > 0) {
int digit = st.empty() ? 0 : st.pop();
int sum = digit + adder + carry;
carry = sum >= 10 ? 1 : 0;
sum = sum >= 10 ? sum - 10 : sum;
ListNode cur = new ListNode(sum);
cur.next = dummy.next;
dummy.next = cur;
adder = 0;
}
return dummy.next;
}
}
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33
C++原因的代码如下：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* plusOne(ListNode* head) {
stack<int> st;
while (head) {
st.push(head->val);
head = head->next;
}
int carry = 0;
ListNode* dummy = new ListNode(0);
int adder = 1;
while (!st.empty() || adder != 0 || carry > 0) {
int digit = 0;
if (!st.empty()) {
digit = st.top();
st.pop();
}
int sum = digit + adder + carry;
carry = sum >= 10 ? 1 : 0;
sum = sum >= 10 ? sum - 10 : sum;
ListNode* cur = new ListNode(sum);
cur->next = dummy->next;
dummy->next = cur;
adder = 0;
}
return dummy->next;
}
};
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38
Python 代码如下：
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution(object):
def plusOne(self, head):
st = []
while head:
st.append(head.val)
head = head.next
carry = 0
dummy = ListNode(0)
adder = 1
while st or adder != 0 or carry > 0:
digit = st.pop() if st else 0
sum = digit + adder + carry
carry = 1 if sum >= 10 else 0
sum = sum - 10 if sum >= 10 else sum
cur = ListNode(sum)
cur.next = dummy.next
dummy.next = cur
adder = 0
return dummy.next
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
复杂度分析：
- 时间复杂度：O(max(N))，N 是链表的长度；
- 空间复杂度：O(1)，只使用了常数的空间。
类似题目
看完本文，你可以解决以下题目：
- 415. 字符串相加open in new window
- [2. 两数相加open in new window][2. _open in new window]
- 445. 两数相加 IIopen in new window
- 369. 给单链表加一open in new window
- 66. 加一open in new window
- 989. 数组形式的整数加法open in new window
- 67. 二进制求和open in new window
总结
1、 「求加法」系列题目都不难，其实就是「列竖式」计算；
2、 需要注意的是：
1、 while循环结束条件；
2、 遍历「加数」不要越界；
3、 进位；
4、 链表在插入的时候如何进行反转；
DDKK.COM 弟弟快看-教程，程序员编程资料站，版权归原作者所有
本文经作者：负雪明烛 授权发布，任何组织或个人未经作者授权不得转发