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 分析：
递归做法：
/**
* 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) {
if (head == null)
return null;
int carry = helper(head);
if (carry == ) {
ListNode newHead = new ListNode();
newHead.next = head;
return newHead;
} else {
return head;
}
} public int helper(ListNode head) {
if (head == null)
return ; int carry = helper(head.next);
int value = head.val;
head.val = (value + carry) % ;
carry = (value + carry) / ;
return carry;
}
}
方法二：
先reverse, 加一，再reverse.
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
private ListNode reverse(ListNode head) {
ListNode prev = null;
ListNode current = head;
ListNode next = null;
while (current != null) {
next = current.next;
current.next = prev;
prev = current;
current = next;
}
return prev;
} public ListNode plusOne(ListNode head) { head = reverse(head);
ListNode newHead = head;
if (head == null)
return null;
int carry = ; ListNode prev = null;
while (head != null) {
int value = head.val;
head.val = (value + carry) % ;
carry = (value + carry) / ;
prev = head;
head = head.next;
} if (carry == ) {
ListNode end = new ListNode();
prev.next = end;
} return reverse(newHead);
}
}