Increment a number given in the form of linked list

Given a large number represented in the form of a linked list, Write code to increment the number in-place. For example:

This question is related to the one we did earlier where we added two numbers given in the form of linked list. Both the methods discussed in that post are valid here also.
Solution-1: Reverse the list

 1. Reverse the list.
 2. Add one to first element in the list, If there is any carry then keep adding it
    to the next node till either, the carry becomes zero or end of the list is reached.
 3. If Carry becomes zero, then return.
    Else if carry is one but End of list is reached.
        Allocate a new node with value 1 and append it to the list.

the code for this is simple and can be derived from the earlier post. This solution takes linear time and constant extra memory, however the below solution is little better then this one.

Solution-2 Best Solution

The best solution for this can do it in O(n) time using O(1) extra space. This is a special case where we are just adding one. The only place where a carry can happen is when there is 9 at the end. And the carry will propagate only till there are 9’s (from the end) because the maximum carry is 1 only and if we get a digit < 9 then there wont be any carry passed to the left.

So we keep two pointers. One to reach end of the list and other will point to the right most digit that is < 9. In the below code, ‘pre’ will always point to the rightmost digit

1. There is only one Node (Single digit number) In this case ‘pre’ will point to the first Node.
2. All the digits can be 9 (eg. 9999) In which case one extra node need to be added at the head of the list.
3. The entire list is null (which means that the number is zero), in this case we need to add a node and assign 1 to it.

Below is the code for the above logic.

Code:

/* Increment the number represented by the list by one.
 * Return pointer to head of the new list (List may change).
 */
Node* increment(Node* head)
{
   // If no node then the number is assumed to be zero.
   if(head == NULL){ return new Node(1); }
   // pre will point to the rightmost node with value < 9
   Node* prev = head;
   Node* cur = head;
   while(cur != NULL)
   {
      cur = cur->next;
      if( cur!= NULL && cur->data != 9)
         prev = cur;
   }
   // At this point pre will be set to point to the right most element with value  100
      prev = new Node(1);
      prev->next = head;
      while(head != NULL)
      {
         head->data = 0;
         head = head->next;
      }
      head = prev;
   }
   else
   {
      // We need to increment the node pointed to by pre.
      // and set all the node after pre to zero
      prev->data += 1;
      prev = prev->next;
      while(prev!= NULL)
      {
         prev->data = 0;
         prev = prev->next;
      }
   }
   return head;
}