369. Plus One Linked List

Well, I was thinking reverse the list, do increase and reverse the list again in first place. However, I don't think it is expected in the interview because this is so naive. And particularly, if we are not allowed to change the list order then this solution is out. Actually, we can do recursive way because recursion helps us "reverse" the list.

1:  /**  
2:   * Definition for singly-linked list.  
3:   * struct ListNode {  
4:   *   int val;  
5:   *   ListNode *next;  
6:   *   ListNode(int x) : val(x), next(NULL) {}  
7:   * };  
8:   */  
9:  class Solution {  
10:  public:  
11:    ListNode* plusOne(ListNode* head) {  
12:      if (dfs(head) == 0) return head;  
13:      else {  
14:        ListNode *node = new ListNode(1);  
15:        node->next = head;  
16:        return node;  
17:      }  
18:    }  
19:    int dfs(ListNode *head) {  
20:      if (head == NULL) return 1;  
21:      int carry = dfs(head->next);  
22:      if (carry == 0) return 0;  
23:      int val = head->val + 1;  
24:      head->val = val % 10;  
25:      return val / 10;  
26:    }  
27:  };