a general method for solving this problem! time complexity is still O(n)


  • 0
    C
    
    /**
     * 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 head;
            
            ListNode current=reverse(head);
            head=current;
            int m=1;
            
            while(current!=null){
                int a=(current.val+m)%10;
                m=(current.val+m)/10;
                current.val=a;
                if(m==0||current.next==null) break;
                current=current.next;
            }
            if(m!=0){
                 current.next=new ListNode(1);
            }
            current=reverse(head);
            
            return current;
        }
        public ListNode reverse(ListNode head){
            ListNode pre=null;
            ListNode current=head;
            while(current!=null){
                ListNode temp=current;
                current=current.next;
                temp.next=pre;
                pre=temp;
            }
            return pre;
        }
    }
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.