Java O(n) time, O(1) space


  • 0
    Y
    reverse the LinkedList to operate from the less significant bit.
    
    
    public class Solution {
    public ListNode plusOne(ListNode head) {
        ListNode newHead = reverseList(head);
        int carry = 1;
        ListNode curr = newHead;
        while (curr != null) {
            int val = curr.val + carry;
            curr.val = val % 10;
            if (val < 10) {
                carry = 0;
                break;
            }
            curr = curr.next;
        }
        if (carry == 1) {
            ListNode res = new ListNode(1);
            res.next = reverseList(newHead);
            return res;
        } else {
            return reverseList(newHead);
        }
    }
    public ListNode reverseList(ListNode head) {
        ListNode newHead = null;
        while (head != null) {
            ListNode next = head.next;
            head.next = newHead;
            newHead = head;
            head = next;
        }
        return newHead;
    }
    

    }


Log in to reply
 

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