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解法1: reverse -> +1 -> reverse
解法2:Two Pointer
第一个pointer loop整个 list, 如果有不为9的数reference给第二个pointer。目的是使得第二个pointer指向从右数的第一个不为9的数,这样就可以加
loop到最后 p2.val++,P2后边如果还有点,全换成0
这里dummy可以handle 9->9->9 这种情况
public ListNode plusOne(ListNode head) {
//use two pointers
ListNode dummy = new ListNode(0);
ListNode p1 = dummy;
ListNode p2 = dummy;
dummy.next = head;
while(p1.next!=null){
p1 = p1.next;
if(p1.val != 9){
p2 = p1;
}
}
if(p1.val!=9){
p1.val++;
}else{
p2.val++;
while(p2.next!=null){
p2 = p2.next;
p2.val = 0;
}
}
if(dummy.val == 0) return dummy.next;
return dummy;
}
没有评论:
发表评论