369. Plus One Linked List

 

leetcode.com/problems/plus-one-linked-list/

 

 

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 1:

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

Example 2:

Input: head = [0] Output: [1]

 

Constraints:

• The number of nodes in the linked list is in the range [1, 100].
• 0 <= Node.val <= 9
• The number represented by the linked list does not contain leading zeros except for the zero itself. 

 

 

Solution

---

Overview.

"Plus One" is a subset of a problem set "Add Number", and the solution patterns are the same.

All these problems could be solved in linear time, and the question here is how to solve without using addition operation or how to fit into constant space complexity.

The choice of algorithm should be based on input format:

1. Integers. Usually addition operation is not allowed for such a case. Use Bit Manipulation Approach. Here is an example: Add Binary.

2. Strings. Use schoolbook bit by bit computation. Note, that to fit into constant space is not possible for languages with immutable strings, for ex. for Java and Python. Here is an example: Add Binary.

3. Arrays. The same textbook addition. Here is an example: Add to Array Form of Integer.

4. Linked Lists, current problem. Sentinel Head + Textbook Addition.

Note, that straightforward idea to convert everything into integers and then use addition could be risky for Java interviews because of possible overflow issues, here is in more details.

---

Approach 1: Sentinel Head + Textbook Addition.

Textbook Addition

Let's identify the rightmost digit which is not equal to nine and increase that digit by one. All the following nines should be set to zero.

Here is the simplest use case which works fine.

Here is more difficult case which still passes.

And here is the case which breaks everything.

Sentinel Head

To handle the last use case, one needs so called Sentinel Node. Sentinel nodes are widely used for trees and linked lists as pseudo-heads, pseudo-tails, etc. They are purely functional, and usually don't hold any data. Their main purpose is to standardize the situation to avoid edge case handling.

For example, here one could add pseudo-head with zero value, and hence there will always be not-nine node.

Algorithm

• Initialize sentinel node as ListNode(0) and set it to be the new head: sentinel.next = head.

• Find the rightmost digit not equal to nine.

• Increase that digit by one.

• Set all the following nines to zero.

• Return sentinel node if it was set to 1, and head sentinel.next otherwise.

Implementation

class Solution {
  public ListNode plusOne(ListNode head) {
    // sentinel head
    ListNode sentinel = new ListNode(0);
    sentinel.next = head;
    ListNode notNine = sentinel;

    // find the rightmost not-nine digit
    while (head != null) {
      if (head.val != 9) notNine = head;
      head = head.next;
    }
    
    // increase this rightmost not-nine digit by 1
    notNine.val++;
    notNine = notNine.next;
    
    // set all the following nines to zeros
    while (notNine != null) {
      notNine.val = 0;
      notNine = notNine.next;
    }
    
    return sentinel.val != 0 ? sentinel : sentinel.next;
  }
}

 

 

 

Complexity Analysis

• Time complexity : \mathcal{O}(N)O(N) since it's not more that two passes along the input list.

• Space complexity : \mathcal{O}(1)O(1).

 

 

 

 

 

dfs로 풀면 공간복잡도가 o(N)이라는 문제가 있다.

class Solution {
    int dfs(ListNode node) {
        if(node == null) return 1;
        
        int num = node.val + dfs(node.next);
        node.val = num % 10;
        return num/10;
    }
    public ListNode plusOne(ListNode head) {
        int carry = dfs(head);
        if(carry > 0) {
            ListNode carryNode = new ListNode(carry);
            carryNode.next = head;
            head = carryNode;
        }
        return head;
    }
}