Plus One Linked List

Problem: Plus One Linked List

We can store all the nodes in a stack when we try to reach the last node. When we got carries to add, we can pop nodes from the stack and add it.

Code in Python:

# 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 = []
        node = head
        while node != None:
            stack.append(node)
            node = node.next

        carry = 1
        while stack:
            if stack[-1].val == 9:
                stack[-1].val = 0
                stack.pop()
            else:
                stack[-1].val += 1
                carry = 0
                break

        if carry == 1:
            newHead = ListNode(1)
            newHead.next = head
            head = newHead
        return head