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.
Example :
Input: [1,2,3]
Output: [1,2,4]
这道题给了我们一个链表，用来模拟一个三位数，表头是高位，现在让我们进行加1运算，这道题的难点在于链表无法通过坐标来访问元素，只能通过遍历的方式进行，而这题刚好让我们从链尾开始操作，从后往前，遇到进位也要正确的处理，最后还有可能要在开头补上一位。那么我们反过来想，如果链尾是高位，那么进行加1运算就方便多了，直接就可以边遍历边进行运算处理，那么我们可以做的就是先把链表翻转一下，然后现在就是链尾是高位了，我们进行加1处理运算结束后，再把链表翻转回来即可，参见代码如下：
解法一：
class Solution {
public:
ListNode* plusOne(ListNode* head) {
if (!head) return head;
ListNode *rev_head = reverse(head), *cur = rev_head, *pre = cur;
int carry = 1;
while (cur) {
pre = cur;
int t = cur->val + carry;
cur->val = t % 10;
carry = t / 10;
if (carry == 0) break;
cur = cur->next;
}
if (carry) pre->next = new ListNode(1);
return reverse(rev_head);
}
ListNode* reverse(ListNode *head) {
if (!head) return head;
ListNode *dummy = new ListNode(-1), *cur = head;
dummy->next = head;
while (cur->next) {
ListNode *t = cur->next;
cur->next = t->next;
t->next = dummy->next;
dummy->next = t;
}
return dummy->next;
}
};
我们也可以通过递归来实现，这样我们就不用翻转链表了，通过递归一层一层的调用，最先处理的是链尾元素，我们将其加1，然后看是否有进位，返回进位，然后回溯到表头，加完进位，如果发现又产生了新的进位，那么我们在最开头加上一个新节点即可，参见代码如下：
解法二：
class Solution {
public:
ListNode* plusOne(ListNode* head) {
if (!head) return head;
int carry = helper(head);
if (carry == 1) {
ListNode *res = new ListNode(1);
res->next = head;
return res;
}
return head;
}
int helper(ListNode *node) {
if (!node) return 1;
int carry = helper(node->next);
int sum = node->val + carry;
node->val = sum % 10;
return sum / 10;
}
};
下面这种方法比较巧妙了，思路是遍历链表，找到右起第一个不为9的数字，如果找不到这样的数字，说明所有数字均为9，那么在表头新建一个值为0的新节点，进行加1处理，然后把右边所有的数字都置为0即可。举例来说：
比如1->2->3，那么第一个不为9的数字为3，对3进行加1，变成4，右边没有节点了，所以不做处理，返回1->2->4。
再比如说8->9->9，找第一个不为9的数字为8，进行加1处理变成了9，然后把后面的数字都置0，得到结果9->0->0。
再来看9->9->9的情况，找不到不为9的数字，那么再前面新建一个值为0的节点，进行加1处理变成了1，把后面的数字都置0，得到1->0->0->0。
解法三：
class Solution {
public:
ListNode* plusOne(ListNode* head) {
ListNode *cur = head, *right = NULL;
while (cur) {
if (cur->val != 9) right = cur;
cur = cur->next;
}
if (!right) {
right = new ListNode(0);
right->next = head;
head = right;
}
++right->val;
cur = right->next;
while (cur) {
cur->val = 0;
cur = cur->next;
}
return head;
}
};
最后这种解法是解法二的迭代写法，我们用到栈，利用栈的先进后出机制，就可以实现从后往前的处理节点，参见代码如下：
解法四：
class Solution {
public:
ListNode* plusOne(ListNode* head) {
stack<ListNode*> s;
ListNode *cur = head;
while (cur) {
s.push(cur);
cur = cur->next;
}
int carry = 1;
while (!s.empty() && carry) {
ListNode *t = s.top(); s.pop();
int sum = t->val + carry;
t->val = sum % 10;
carry = sum / 10;
}
if (carry) {
ListNode *new_head = new ListNode(1);
new_head->next = head;
head = new_head;
}
return head;
}
};
类似题目：
参考资料：
https://leetcode.com/problems/plus-one-linked-list/
https://leetcode.com/discuss/111165/2-accepted-java-solution
https://leetcode.com/discuss/111205/simple-solution-use-recursion
https://leetcode.com/discuss/111157/9-lines-recursive-without-helper
https://leetcode.com/discuss/111155/java-stack-solution-with-inline-explanation
LeetCode All in One 题目讲解汇总(持续更新中…)
转载请注明来源于 Grandyang 的博客 (grandyang.com)，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 grandyang@qq.com
