369. Plus One Linked List

 

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;
    }
};

 

类似题目:

Plus One

 

参考资料:

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

💰


微信打赏


Venmo 打赏

(欢迎加入博主的知识星球,博主将及时答疑解惑,并分享刷题经验与总结,试运营期间前五十位可享受半价优惠~)

×

Help us with donation