Plus One Linked List

LeetCode #369

Description:

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:

Example:
Input:
1->2->3

Output:
1->2->4

Idea:

俩种方法，一种先reverse，相加，然后再reverse。 另一种就是DFS，很简洁。

Code:

Solution 1 similar to DFS

class Solution {
public:
    ListNode* plusOne(ListNode* head) {
        if(head==NULL) return NULL;

        int carry = plusOneRec(head);
        if(carry==0) return head;
        else{
            // cannot do dummy(1), return &dummy, dummy is a temporary object.
            ListNode *new_head = new ListNode(1);
            new_head->next=head;
            return new_head;
        }
    }

    // Recursive, like DFS
    int plusOneRec(ListNode *head){
        if(head==NULL) return 1;

        int add_digit = head->val + plusOneRec(head->next);
        head->val = add_digit%10;
        return add_digit/10;
    } 
};

Solution 2 reverse first, add, then reverse back.

class Solution {
public:
    ListNode* plusOne(ListNode* head) {
        if(head==NULL) return NULL;

        reverseList(head);

        int carry=1;
        ListNode *curr=head;
        ListNode *pre;

        while(curr!=NULL && carry!=0){
            int add_digit = curr->val + carry;
            curr->val = add_digit%10;
            carry = add_digit/10;
            pre=curr;
            curr=curr->next;
        }

        if(carry==1){
            pre->next = new ListNode(carry);
        }

        reverseList(head);

        return head;
    }

    void reverseList(ListNode *& head){
        ListNode *curr=head;
        ListNode *pre=NULL;
        while(curr!=NULL){
            ListNode *tmp=curr->next;
            curr->next=pre;
            pre=curr;
            curr=tmp;
        }
        head=pre;
    }

};