Simple Python iterative solution using stack. Beat 94%


  • 0
    H

    Each digit is in range [0-9], use c to track carry. Update c for the higher digit to use. If c = 1 after processing all nodes, create a new ListNode with value 1.

    class Solution(object):
        def plusOne(self, head):
            """
            :type head: ListNode
            :rtype: ListNode
            """
            s = []
            p = head
            while p:
                s.append(p)
                p = p.next
            c = 1
            cur_digit = None
            while s:
                cur = s.pop()
                cur_digit = cur.val + c
                if cur_digit == 10:
                    c = 1
                    cur.val = 0
                else:
                    c = 0
                    cur.val = cur_digit
            if c == 1:
                new_head = ListNode(1)
                new_head.next = head
                head = new_head
            
            return head
    

Log in to reply
 

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