Python solution with detailed explanation


  • 0
    G

    Solution

    Plus One Linked List https://leetcode.com/problems/plus-one-linked-list/

    Algorithm

    • The algorithm is clear. First reverse, then add 1, then reverse again
    class Solution(object):
        def reverse(self, root):
            prev, curr = None, root
            while curr:
                temp, curr.next = curr.next, prev
                prev, curr = curr, temp
            return prev
        
        def add1(self, root):
            curr, carry = root, 0
            curr.val += 1
            while curr.next:
                new_val = int((curr.val + carry) % 10)
                carry = (curr.val + carry) // 10
                curr.val, curr = new_val, curr.next
            if curr.val + carry >= 10:
                curr.val = int((curr.val + carry) % 10)
                curr.next = ListNode(1)
            else:
                curr.val = curr.val + carry
            return root
        
        def plusOne(self, root):
            """
            :type head: ListNode
            :rtype: ListNode
            """
            if root == None:
                return ListNode(1)
            root = self.reverse(root)
            self.add1(root)
            return self.reverse(root)
    

Log in to reply
 

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