2016年10月21日星期五

369. 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
解法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;  
   }  

没有评论:

发表评论