plusOne

Problem description:

Given a non-negative integer represented as a linked list of digits, plus one to the integer.

The digits are stored such that the most significant digit is at the head of the list.

One basic or brute force approach is to reverse the list, again while reversing back, add one and proceed.

Below is my solution with this approach:

/* Brute force approach is to reverse the list
 again while reversing back , add one */
struct ListNode* plusOne(struct ListNode* head){
    struct ListNode *tmp, *nxt;
    
    if (!head)
        return NULL;
    nxt = head->next;
    head->next = NULL;
    while (nxt!=NULL){
        tmp = nxt->next;
        nxt->next = head;
        head = nxt;
        nxt = tmp;
    }
    char carry=0;
    nxt = head->next;
    head->val +=1;
    if (head->val >=10){
        carry =1;
        head->val -=10;
    }
    head->next = NULL;
    while (nxt!=NULL){
        tmp = nxt->next;
        nxt->val += carry;
        if (nxt->val >= 10){
            carry =1;
            nxt->val -=10;
        }else
            carry = 0;
        nxt->next = head;
        head = nxt;
        nxt = tmp;
    }
    if (carry){
        tmp = (struct ListNode *)malloc(sizeof(struct ListNode));
        tmp->val = carry;
        tmp->next = head;
        head = tmp;
    }
    return head;
}

The approach requires double-time traversal.

But the person who designed this problem may not expect to reverse and reverse back. There is some trick to optimize.

The trick is to avoid another traversal wherever possible.

• In the case of 123, adding one will lead to only the last node change, where we can avoid reversal traversal.
• In case 219, adding one will lead to 2 nodes change, where we can avoid reversal traversal before 1.
• But in case 19999, it is compulsory to traverse back the entire list.
  To achieve this we need not reverse the list.
  Go till the end of the list, save the last pointer which is pointing to the value of not 9 in the list.
  the In next traversal, we only need to traverse from this last pointer to the end of the list.
  So no reversal of the list is required.

Below is my solution which I learned this approach from Leetcode:

/* Brute force approach is to reverse the list
 again while reversing back , add one 
 But this is general approach.
 there is no great
 This involves double time traversal.
 Trick is to avoid extra nodes traversal wherever possible.
 In case of 123, add one will lead to only last node change, where we can avoid reversal traversal.
 In case 219, add one will lead to 2 nodes change, where we can avoid reversal traversal before 1.
 But in case 19999, it is compulsory to traverse back entire list.
 
 To achieve this we need not reverse the list.
 Go till the end of list, save the last pointer which is pointing to the value of not 9 in the list.
 In next traversal, we only need to traverse from this last pointer to the end of list.
 So no reversal of list is required. 
 */
struct ListNode* plusOne(struct ListNode* head){
    struct ListNode *tmp, *nn = NULL;
    
    if (!head)
        return NULL;
    tmp = head;
    while (tmp!= NULL){
        if (tmp->val != 9) nn = tmp;
        tmp = tmp->next;
    }
    
    /* in case of 999, nn will be NULL */
    /* if nn is NULL, allocate a node at the beginning and travere till the end to make all values to 0 */
    if (!nn)
    {
        nn = (struct ListNode *)malloc(sizeof(struct ListNode));
        nn->val = 1;
        nn->next = head;
        head = nn;
    } else nn->val +=1;
    nn= nn->next;
    while (nn!=NULL){
        nn->val = 0;
        nn = nn->next;
    }
    return head;
}