369. Plus One Linked List

做题历程：

1. 2016/Jul/07 独立解决

本题难度尚可，不过其实也没有太多算法可言，就是纯粹考Linked List的理解和操作。 核心就是用recursive DFS一直深入到尾节点，记住要在每次调用下一层的recursive function和本function的之间进行进位操作，多说无益，代码如下：

/**
 * 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) {
        if (head == nullptr) {
            return nullptr;
        }
        ListNode* virtual_node = new ListNode(0);
        virtual_node->next = head;
        ListNode* res = helper(virtual_node);
        return res->val == 0 ? res->next : res;
    }
private:
    ListNode* helper(ListNode* node) {
        if (node->next == nullptr) {
            node->val += 1;
        }
        else {
            node->next = helper(node->next);
            if (node->next->val == 10) {
                node->next->val = 0;
                node->val += 1;
            }
        }
        return node;
    }
};