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)
      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;
  }
}

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* i = dummy;
    dummy->next = head;

    while (head) {
      if (head->val != 9)
        i = head;
      head = head->next;
    }
    // i point to the rightmost non-9 node

    ++i->val;
    while (i->next) {
      i->next->val = 0;
      i = i->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 i = dummy;
    dummy.next = head;

    while (head != null) {
      if (head.val != 9)
        i = head;
      head = head.next;
    }
    // i point to the rightmost non-9 node

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

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