Clear Java Solution: Time O(n)


  • 0
    Z
        /*
        Step 1: Reverse list
        Step 2: Add 1 and update the list
        Step 3: Reverse list
        */
        public ListNode plusOne(ListNode head) {
            ListNode newHead = reverse(head);
            ListNode cur = newHead;
            ListNode prev = null;
            int carry = 1;
            
            while (cur != null) {
                int sum = carry + cur.val;
                cur.val = sum % 10;
                carry = sum / 10;
                prev = cur;
                cur = cur.next;
            }
            if (carry == 1) {
                prev.next = new ListNode(1);
            }
            newHead = reverse(newHead);
    
            return newHead;
        }
        
        private ListNode reverse(ListNode node) {
            ListNode cur = node;
            ListNode prev = null;
            
            while (cur != null) {
                ListNode next = cur.next;
                cur.next = prev;
                prev = cur;
                cur = next;
            }
            return prev;
        }
    
    

Log in to reply
 

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