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->3

Output:
1->2->4

O(n) time O(n) space, using a stack

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode plusOne(ListNode head) {
        Stack<ListNode> stack = new Stack();
        while (head != null) {
            stack.push(head);
            head = head.next;
        }
        ListNode rightDigit = null;
        int carry = 1;
        ListNode result = null;
        while (!stack.empty()) {
            ListNode current = stack.pop();
            result = new ListNode((current.val + carry) % 10);
            carry = (current.val + carry) / 10;
            result.next = rightDigit;
            rightDigit = result;
        }
        if (carry == 1) {
            result = new ListNode(1);
            result.next = rightDigit;
        }
        return result;
    }
}

O(n) time O(n) space recursive solution

from Leetcode discussion board

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Solution {
     public ListNode plusOne(ListNode head) {
         if (plusOneHelper(head) == 0) {
             return head;
         }
         //need addtional node
         ListNode newHead = new ListNode(1);
         newHead.next = head;
         return newHead;
     }
     
     // plus one for the rest of the list starting from node and return carry
  //because last node.next is null, let null return 1 and it is equivalent to  "plus one" to the least significant digit

     private int plusOneHelper(ListNode node) {
         if (node == null) {
             return 1;
         }
         int sum = node.val + plusOneHelper(node.next);
         node.val = sum % 10;
         return sum / 10;
     }
 }

O(n) time, O(1) space

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
public class Solution {
    public ListNode plusOne(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode regular = dummy;
        ListNode notNine = dummy;
        
        while (regular.next != null) {
            regular = regular.next;
            // find the least significant non-9 dight
            if (regular.val != 9) {
                notNine = regular;
            }
        }
        
        if (regular.val != 9) {
            regular.val++;
        }else{
        // case for one or more 9s
            notNine.val++;
            notNine = notNine.next;
            while (notNine != null) {
                notNine.val = 0;
                notNine = notNine.next;
            }
        }
        
        return dummy.val == 0 ? dummy.next : dummy;
    }
}

Reverse, increase, then reverse again, O(n) time, O(1) time

this posts