题解 | JAVA 递归#给单链表加一# [P1]

对于链表，如果要从后往前操作，一般就是用递归最方便
每次递归完返回进位（0 或者 1).

链表最前方加上个sentinal node以防最高位进位，e.g. (99+1=100)
时间 O(n)
空间 O(n): basecase时每一位的node都在栈上

import java.util.*;

public class Solution {
    public ListNode plusOne (ListNode head) {
      ListNode sentinal = new ListNode(0);
      sentinal.next = head;
      plusOneRecurse(sentinal);
      
      // 如果没有最高位进位(e.g. 98+1=99), 返回值就不包括sentinal
      if (sentinal.val == 0) {
        return sentinal.next;
      }
      // 如果有最高位进位(e.g. 99+1=100), 返回值就包括sentinal
      return sentinal;
    }
  
    private int plusOneRecurse(ListNode head) {
      // basecase返回1用于实现“加一”
      if (head == null) return 1;
   
      int remainder = plusOneRecurse(head.next);
      
      if (remainder + head.val == 10) {
        head.val = 0;
        return 1;
      } else {
        head.val += remainder;
        return 0;
      }
    }
}