How hard is LeetCode 369. Plus One Linked List?

LeetCode 369. Plus One Linked List is rated Medium on LeetCode.

What is the time complexity of LeetCode 369. Plus One Linked List?

The Python solution on this page runs in O(n), where n is the length of the linked list.

What is the space complexity of LeetCode 369. Plus One Linked List?

The Python solution on this page uses O(1) auxiliary space.

What topics does LeetCode 369. Plus One Linked List cover?

LeetCode 369. Plus One Linked List is tagged Linked List and Math on LeetCode.

Is LeetCode 369. Plus One Linked List a premium problem?

Yes. LeetCode 369. Plus One Linked List is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.

Plus One Linked List — LeetCode 369 Python Solution

MediumLeetCode PremiumLinked ListMath

Problem: #369
Pattern: Linked List
Reading time: 3 min
Source: leetcode.com

The problem

Given a non-negative integer represented as a linked list of digits, plus one to the integer. The digits are stored such that the most significant digit is at the head of the list.

Example

Input: head = [1,2,3]
Output: [1,2,4]

Python solution

Python

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def plusOne(self, head: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(0, head)
        target = dummy
        while head:
            if head.val != 9:
                target = head
            head = head.next
        target.val += 1
        target = target.next
        while target:
            target.val = 0
            target = target.next
        return dummy if dummy.val else dummy.next

Complexity

Measure	Complexity
Time	O(n), where n is the length of the linked list
Space	O(1) auxiliary

Pattern: Linked List

Rewire pointers in place, with a dummy head and a saved next to keep it safe. LeetCode 369. Plus One Linked List is filed here because LeetCode tags it Linked List, which is the vocabulary this hub collects.

The linked list guide has the Python template for the pattern and the 75 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 369. Plus One Linked List?: LeetCode 369. Plus One Linked List is rated Medium on LeetCode.
What is the time complexity of LeetCode 369. Plus One Linked List?: The Python solution on this page runs in O(n), where n is the length of the linked list.
What is the space complexity of LeetCode 369. Plus One Linked List?: The Python solution on this page uses O(1) auxiliary space.
What topics does LeetCode 369. Plus One Linked List cover?: LeetCode 369. Plus One Linked List is tagged Linked List and Math on LeetCode.
Is LeetCode 369. Plus One Linked List a premium problem?: Yes. LeetCode 369. Plus One Linked List is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.