369- Plus One Linked List  **Question Editorial Solution

 My Submissions

Total Accepted: 1189 Total Submissions: 2373 Difficulty: Medium

Given a non-negative number represented as a singly linked list of digits, plus one to the number. The digits are stored such that the most significant digit is at the head of the list. Example: Input:1->2->3Output:1->2->4

Hide Company Tags  Google Hide Tags  Linked List Hide Similar Problems  (E) Plus One

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34


 public ListNode plusOne(ListNode head) {
  /*
   * At the first glance, I want to reverse the inputs, add one, then
   * reverse back. But that is too intuitive and I don't think this is an
   * expected solution. Then what kind of alg would adding one in reverse
   * way for list?
   * 
   * Recursion! With recursion, we can visit list in reverse way! So here is my
   * recursive solution.
   * https://discuss.leetcode.com/topic/49541/java-recursive-solution
   */
  if (dfs(head) == 0) {
   return head;
  } else {
   ListNode newHead = new ListNode(1);
   newHead.next = head;
   return newHead;
  }
 }

 // Recursion solution
 public int dfs(ListNode head) {
  if (head == null)
   return 1;

  int carry = dfs(head.next);
  if (carry == 0)
   return 0;

  int val = head.val + 1;
  head.val = val % 10;
  return val / 10;
 }