369. Plus One Linked List (Medium)

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:

Solution 1: 3ms

这道题给了我们一个链表，用来模拟一个三位数，表头是高位，现在让我们进行加1运算，这道题的难点在于链表无法通过坐标来访问元素，只能通过遍历的方式进行，而这题刚好让我们从链尾开始操作，从后往前，遇到进位也要正确的处理，最后还有可能要在开头补上一位。那么我们反过来想，如果链尾是高位，那么进行加1运算就方便多了，直接就可以边遍历边进行运算处理，那么我们可以做的就是先把链表翻转一下，然后现在就是链尾是高位了，我们进行加1处理运算结束后，再把链表翻转回来即可，参见代码如下：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* plusOne(ListNode* head) {
        ListNode* cur = head->next, *pre = head;
        pre->next = NULL;
        while (cur) {
            ListNode* tmp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = tmp;
        }

        bool addOne = true;
        cur = pre->next, pre->next = NULL;
        while (cur) {
            if (addOne) {
                if (pre->val != 9) {
                    pre->val++;
                    addOne = false;
                } else {
                    pre->val = 0;
                }
            }

            ListNode* tmp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = tmp;
        }

        if (addOne) {
            if (pre->val != 9) {
                pre->val++;
            } else {
                pre->val = 0;
                head = new ListNode(1);
                head->next = pre;
            }
        }
        return head;
    }
};

Solution 2: recursion 3ms

我们也可以通过递归来实现，这样我们就不用翻转链表了，通过递归一层一层的调用，最先处理的是链尾元素，我们将其加1，然后看是否有进位，返回进位，然后回溯到表头，加完进位，如果发现又差生了新的进位，那么我们在最开头加上一个新节点即可，参见代码如下：

class Solution {
    bool helper(ListNode* head) {
        if (!head) return true;

        if (helper(head->next)) {
            if (head->val == 9) {
                head->val = 0;
                return true;
            } else {
                ++head->val;
                return false;
            }
        } 
        return false;
    }
public:
    ListNode* plusOne(ListNode* head) {
        if (helper(head)) {
            ListNode* tmp = new ListNode(1);
            tmp->next = head;
            return tmp;
        }
        return head;
    }
};

最后这种解法是解法二的迭代写法，我们用到栈，利用栈的先进后出机制，就可以实现从后往前的处理节点，参见代码如下：

version 2: 3ms

class Solution {
public:
    ListNode* plusOne(ListNode* head) {
        stack<ListNode*> s;
        ListNode* cur = head;
        while (cur) {
            s.push(cur);
            cur = cur->next;
        }

        bool addOne = true;
        while (!s.empty()) {
            ListNode* t = s.top(); s.pop();
            if (t->val == 9) {
                t->val = 0;
            } else {
                ++t->val;
                addOne = false;
                return head;
            }
        }

        if (addOne) {
            cur = new ListNode(1);
            cur->next = head;
        }
        return cur;

    }
};

Solution 3: Two Pointers 3ms

下面这种方法比较巧妙了，思路是遍历链表，找到第一个不为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, *firstNot9Pos = NULL;
        while (cur) {
            if (cur->val != 9) firstNot9Pos = cur;
            cur = cur->next;
        }
        if (!firstNot9Pos) {
            firstNot9Pos = new ListNode(0);
            firstNot9Pos->next = head;
            head = firstNot9Pos;
        }
        ++firstNot9Pos->val;
        cur = firstNot9Pos->next;
        while (cur) {
            cur->val = 0;
            cur = cur->next;
        }

        return head;

    }
};