Skip to content

369. Plus One Linked List 👍

Approach 1: Recursive

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
 public:
  ListNode* plusOne(ListNode* head) {
    if (head == nullptr)
      return new ListNode(1);
    if (addOne(head) == 1)
      return new ListNode(1, head);
    return head;
  }

 private:
  int addOne(ListNode* node) {
    const int carry = node->next ? addOne(node->next) : 1;
    const int sum = node->val + carry;
    node->val = sum % 10;
    return sum / 10;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
  public ListNode plusOne(ListNode head) {
    if (head == null)
      return new ListNode(1);
    if (addOne(head) == 1)
      return new ListNode(1, head);
    return head;
  }

  private int addOne(ListNode node) {
    final int carry = node.next == null ? 1 : addOne(node.next);
    final int sum = node.val + carry;
    node.val = sum % 10;
    return sum / 10;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
  def plusOne(self, head: ListNode) -> ListNode:
    if not head:
      return ListNode(1)
    if self._addOne(head) == 1:
      return ListNode(1, head)
    return head

  def _addOne(self, node: ListNode) -> int:
    carry = self._addOne(node.next) if node.next else 1
    summ = node.val + carry
    node.val = summ % 10
    return summ // 10

Approach 2: Iterative

  • Time: $O(n)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
 public:
  ListNode* plusOne(ListNode* head) {
    ListNode* dummy = new ListNode(0);
    ListNode* curr = dummy;
    dummy->next = head;

    while (head != nullptr) {
      if (head->val != 9)
        curr = head;
      head = head->next;
    }
    // `curr` now points to the rightmost non-9 node.

    ++curr->val;
    while (curr->next != nullptr) {
      curr->next->val = 0;
      curr = curr->next;
    }

    return dummy->val == 0 ? dummy->next : dummy;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
  public ListNode plusOne(ListNode head) {
    ListNode dummy = new ListNode(0);
    ListNode curr = dummy;
    dummy.next = head;

    while (head != null) {
      if (head.val != 9)
        curr = head;
      head = head.next;
    }
    // `curr` now points to the rightmost non-9 node.

    ++curr.val;
    while (curr.next != null) {
      curr.next.val = 0;
      curr = curr.next;
    }

    return dummy.val == 0 ? dummy.next : dummy;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
  def plusOne(self, head: ListNode) -> ListNode:
    dummy = ListNode(0)
    curr = dummy
    dummy.next = head

    while head:
      if head.val != 9:
        curr = head
      head = head.next
    # `curr` now points to the rightmost non-9 node.

    curr.val += 1
    while curr.next:
      curr.next.val = 0
      curr = curr.next

    return dummy.next if dummy.val == 0 else dummy