Leetcode: Plus One Linked List

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

Solution: Use Stack, O(N) space

 1 /**
 2  * Definition for singly-linked list.
 3  * public class ListNode {
 4  *     int val;
 5  *     ListNode next;
 6  *     ListNode(int x) { val = x; }
 7  * }
 8  */
 9 public class Solution {
10     public ListNode plusOne(ListNode head) {
11         Stack<ListNode> st = new Stack<ListNode>();
12         while (head != null) {
13             st.push(head);
14             head = head.next;
15         }
16         ListNode dummy = new ListNode(-1);
17         int carry = 1;
18         while (!st.isEmpty() || carry!=0) {
19             int num = 0;
20             if (!st.isEmpty()) num += st.pop().val;
21             if (carry != 0) num += carry;
22             ListNode newNode = new ListNode(num%10);
23             newNode.next = dummy.next;
24             dummy.next = newNode;
25             carry = num / 10;
26         }
27         return dummy.next;
28     }
29 }

my another solution: don't create new node, modify the existed node

 1 public class Solution {
 2     public ListNode plusOne(ListNode head) {
 3         Stack<ListNode> st = new Stack<>();
 4         ListNode dummy = new ListNode(-1);
 5         dummy.next = head;
 6         while (head != null) {
 7             st.push(head);
 8             head = head.next;
 9         }
10         int carry = 1;
11         while (carry != 0 && !st.isEmpty()) {
12             int num = 0;
13             ListNode cur = st.pop();
14             num = carry + cur.val;
15             cur.val = num % 10;
16             carry = num / 10;
17         }
18         if (carry != 0) {
19             ListNode newNode = new ListNode(carry);
20             newNode.next = dummy.next;
21             dummy.next = newNode;
22         }
23         return dummy.next;
24     }
25 }

Solution 3: reverse the inputs, add one, then reverse back

Solution 4: Recursion: what kind of alg would adding one in reverse way for list?

Recursion! With recursion, we can visit list in reverse way!

 1 public ListNode plusOne(ListNode head) {
 2     if( DFS(head) == 0){
 3         return head;
 4     }else{
 5         ListNode newHead = new ListNode(1);
 6         newHead.next = head;
 7         return newHead;
 8     }
 9 }
10 
11 public int DFS(ListNode head){
12     if(head == null) return 1;
13     
14     int carry = DFS(head.next);
15     
16     if(carry == 0) return 0;
17     
18     int val = head.val + 1;
19     head.val = val%10;
20     return val/10;
21 }

Best Solution: Two Pointers, O(1) space

i stand for the right-most non-9 bit, where if there's a carry, i is incremented and the bits after i will be set 0

 1 public class Solution {
 2     public ListNode plusOne(ListNode head) {
 3         ListNode dummy = new ListNode(0);
 4         dummy.next = head;
 5         ListNode i = dummy;
 6         ListNode j = dummy;
 7         
 8         while (j != null) {
 9             if (j.val != 9) {
10                 i = j;
11             }
12             j = j.next;
13         }
14         
15         i.val++;
16         i = i.next;
17         while (i != null) {
18             i.val = 0;
19             i = i.next;
20         }
21         
22         if (dummy.val == 0) {
23             return dummy.next;
24         }
25         
26         return dummy;
27     }
28 }