AC:Reverse+plus1+reverse: O(n)?

  • 0

    It is a bit long and it uses a helper function called reverse() to reverse the linked list. Not sure about its time and space complexity.

    I think time complexity should be O(n) since iterate the linked list takes n(n is the number nodes in the linked list) times and space complexity should be O(1) since it is in-place? Please correct me if I am wrong. Thanks for viewing!

    class Solution(object):
        def plusOne(self, head):
            :type head: ListNode
            :rtype: ListNode
            rev_head = self.reverse(head)
            first = rev_head
            carry = 1
            while first:
                if first.val + carry == 10:
                    first.val = 0
                    carry = 1
                    first.val += carry
                    carry = 0
                first =
            if carry == 1:
                node = ListNode(1)
       = self.reverse(rev_head)
                return node
                return self.reverse(rev_head)
        def reverse(self, head):
            prev = None
            curr = head
            while curr:
                temp = ListNode(0)
                temp =
       = prev
                prev = curr
                curr = temp
            return prev

Log in to reply

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