Simple Java Solution using Stack, runs in O(n) time and O(n) space: with explanation


  • 0
    A

    This is a O(n) solution using stack. We start at the last digit of the number and process all the digits one by one till the first number

    We iterate through the loop and insert all the nodes in a stack so that we can easily process it in the reverse order.

    There are three cases:

    1. When the last digit is less than 9 and incrementing the whole number does not result in a change in the total number of digits:
      Ex: 18,97,4
      In such cases, just increment the last digit and exit

    2.When the last digit is equal to 9 and incrementing the whole number does not result in a change in the total number of digits:
    Ex: 199,29,1999,1299 etc

    In this case set the digit to 0 and move on to the next digit in rev order and repeat. when we reach a digit that is not equal to 9, just increment it and break out of the loop

    3.When the last digit is equal to 9 and incrementing the whole number increases the no of digits by 1.
    Ex: 99, 999 etc
    This is similar to case 2 except that all the digits will be 0 now, so we have to add an extra node with a value 1 at the beginning of the linked list and return it.

    
    public class Solution {
            public ListNode plusOne(ListNode head) {
            if(head==null)
    		return head;
                   
    		Stack<ListNode> stack = new Stack<>();
    		ListNode temp = head;
                  
    		while(temp!= null){
    			stack.add(temp);
    			temp = temp.next;		
    		}
    		
    		while(!stack.isEmpty()){
    			ListNode top = stack.pop();
                         
    			if(top.val<9){
    				top.val = top.val+1;
    				break;
    			}else
    			{
    				top.val= 0;
    			}	
    				
    		}		
    	
    		if(head.val==0)
    		{
    			ListNode newNode = new ListNode(1);
    			newNode.next = head;
    			return newNode;
    		}
    		return head;
            
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.