AC python solution, easy to understand, beat 11% python solution, O(N) time, O(1) space


  • 0
    W

    Definition for singly-linked list.

    class ListNode(object):

    def init(self, x):

    self.val = x

    self.next = None

    class Solution(object):
    def plusOne(self, head):
    """
    :type head: ListNode
    :rtype: ListNode
    """
    stack = []
    curNode = head

        while curNode != None:
            stack.append(curNode)
            curNode = curNode.next
        
    
        lenStack = len(stack)
        #print "lenStack = ", lenStack
        
        if (lenStack == 0):
            return []
        
        inc = (stack[lenStack-1].val + 1 ) / 10
        stack[lenStack-1].val = (stack[lenStack-1].val + 1 ) % 10
        
        for i in range(lenStack-2, -1, -1):
            #print "i = ", i, " val = ", stack[i].val, " old inc = ", inc
            oldInc = inc
            newInc = (stack[i].val + inc) / 10
            #print " new inc = ", inc
            stack[i].val = (stack[i].val + oldInc) % 10
            #print "new val = ", stack[i].val
            inc = newInc
    
            
        #print "final inc = ", inc
        if (inc == 1):
            newHead = ListNode(1)
            newHead.next = head
            
            return newHead
            
        return head

Log in to reply
 

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