Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

369. Plus One Linked List

Time: $O(n)$

Space: $O(n)$

			


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




			


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




			


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