## Wednesday, June 29, 2016

### LeetCode 369 - Plus One Linked List

http://www.cnblogs.com/grandyang/p/5626389.html
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
```
X. http://blog.csdn.net/jmspan/article/details/51780132
1.     private ListNode reverse(ListNode head) {
2.         ListNode prev = null;
3.         ListNode current = head;
4.         while (current != null) {
5.             ListNode next = current.next;
6.             current.next = prev;
7.             prev = current;
8.             current = next;
9.         }
10.         return prev;
11.     }
12.     public ListNode plusOne(ListNode head) {
13.         if (head == nullreturn null;
14.         ListNode reversed = reverse(head);
15.         reversed.val ++;
16.         ListNode current = reversed;
17.         while (current != null && current.val >= 10) {
18.             current.val -= 10;
19.             if (current.next == null) {
20.                 current.next = new ListNode(1);
21.             } else {
22.                 current.next.val ++;
23.             }
24.             current = current.next;
25.         }
26.         reversed = reverse(reversed);
27.         return reversed;
28.     }

```    ListNode* plusOne(ListNode* head) {
ListNode *rev_head = reverse(head), *cur = rev_head, *pre = cur;
int carry = 1;
while (cur) {
pre = cur;
int t = cur->val + carry;
cur->val = t % 10;
carry = t / 10;
if (carry == 0) break;
cur = cur->next;
}
if (carry) pre->next = new ListNode(1);
}
ListNode* reverse(ListNode *head) {
ListNode *dummy = new ListNode(-1), *cur = head;
while (cur->next) {
ListNode *t = cur->next;
cur->next = t->next;
t->next = dummy->next;
dummy->next = t;
}
return dummy->next;
}```
X.
``````        public ListNode plusOne(ListNode head) {
if (plusOneHelper(head) == 0) {
}
ListNode newHead = new ListNode(1);
}

// 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;
}``````
https://leetcode.com/discuss/111104/java-recursive-solution
Recursion! With recursion, we can visit list in reverse way!

``````public ListNode plusOne(ListNode head) {
ListNode dummy = new ListNode(0);
helper(dummy);
return dummy.val == 0 ? head : dummy;
}

private int helper(ListNode node){
if(node == null) return 1;
node.val += helper(node.next);
if(node.val <= 9) return 0;
node.val %= 10;
return 1;
}``````

```    ListNode* plusOne(ListNode* head) {
int carry = helper(head);
if (carry == 1) {
ListNode *res = new ListNode(1);
return res;
}
}
int helper(ListNode *node) {
if (!node) return 1;
int carry = helper(node->next);
int sum = node->val + carry;
node->val = sum % 10;
return```
If the +1 was already handled without further carry, then the result is the given head node. Otherwise it's a new node (with carry value 1). In other words, a carry-node is created at the end and gets carried towards the front until it has been fully integrated.
public ListNode plusOne(ListNode head) { if (head == null) return new ListNode(1); ListNode plused = plusOne(head.next); if (plused != head.next) head.val++; if (head.val <= 9) return head; head.val = 0; plused.next = head; return plused; }

• i stands for the most significant digit that is going to be incremented if there exists a carry
• dummy node can handle cases such as "9->9>-9" automatically
public ListNode plusOne(ListNode head) { ListNode dummy = new ListNode(0); dummy.next = head; ListNode i = dummy; ListNode j = dummy; while (j.next != null) { j = j.next; if (j.val != 9) { i = j; } } if (j.val != 9) { j.val++; } else { i.val++; i = i.next; while (i != null) { i.val = 0; i = i.next; } } if (dummy.val == 0) { return dummy.next; } return dummy; }
public ListNode plusOne(ListNode head) { ListNode dummy = new ListNode(0); dummy.next = head; ListNode i = dummy; ListNode j = dummy; while (j.next != null) { j = j.next; if (j.val != 9) { i = j; } } // i = index of last non-9 digit i.val++; i = i.next; while (i != null) { i.val = 0; i = i.next; } if (dummy.val == 0) return dummy.next; return dummy; }

```    ListNode* plusOne(ListNode* head) {
ListNode *cur = head, *right = NULL;
while (cur) {
if (cur->val != 9) right = cur;
cur = cur->next;
}
if (!right) {
right = new ListNode(0);
}
++right->val;
cur = right->next;
while (cur) {
cur->val = 0;
cur = cur->next;
}
}
```

```    ListNode* plusOne(ListNode* head) {
stack<ListNode*> s;
ListNode *cur = head;
while (cur) {
s.push(cur);
cur = cur->next;
}
int carry = 1;
while (!s.empty() && carry) {
ListNode *t = s.top(); s.pop();
int sum = t->val + carry;
t->val = sum % 10;
carry = sum / 10;
}
if (carry) {
ListNode *new_head = new ListNode(1);
}
}```

https://discuss.leetcode.com/topic/52174/java-o-n-time-o-1-space-short-solution
The idea is to find the first non-nine node from the right.
Increase its val by 1 and change everything behind it to zero.
``````public ListNode plusOne(ListNode head) {
ListNode notNine = new ListNode(0);
for (ListNode node = head; node != null; node = node.next)
if (node.val != 9) notNine = node;
notNine.val += 1;
for (ListNode node = notNine.next; node != null; node = node.next)
node.val = 0;