369. Plus One Linked List
Problem:
Given a non-negative integer represented as non-empty a singly linked list of digits, plus one to the integer.
You may assume the integer do not contain any leading zero, except the number 0 itself.
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
Solutions:
/**
* 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) {
ListNode fakeHead = new ListNode(0);
fakeHead.next = head;
carry(fakeHead);
if (fakeHead.val != 0) {
return fakeHead;
}
return fakeHead.next;
}
private int carry(ListNode node) {
if (node == null) {
return 1;
}
int next = carry(node.next);
if (next == 0) {
return 0;
}
int tmp = node.val + next;
node.val = tmp % 10;
return tmp / 10;
}
}
/**
* 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) {
ListNode cur = head, right = null;
while (cur != null) {
if (cur.val != 9) right = cur;
cur = cur.next;
}
if (right == null) {
right = new ListNode(0);
right.next = head;
head = right;
}
++right.val;
cur = right.next;
while (cur != null) {
cur.val = 0;
cur = cur.next;
}
return head;
}
}