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


  • 0
    L

    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
                else:
                    first.val += carry
                    carry = 0
                first = first.next
                
            if carry == 1:
                node = ListNode(1)
                node.next = self.reverse(rev_head)
                return node
            else:
                return self.reverse(rev_head)
                    
        def reverse(self, head):
            prev = None
            curr = head
            while curr:
                temp = ListNode(0)
                temp = curr.next
                curr.next = 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.