2 Accepted Java Solution


  • 0
    A

    I came up with 2 simple approaches:

    1. everse the list, apply list addition, and reverse back
    2. more optimization: identify the rightmost node whose value is not 9.
      that is: all nodes to its right have val=9. therefore, we will bump the
      value of this right node and set all the vals to right to 0 after
      addition.

    In both cases, must consider overflow; add an additional node if needed.

    Solution I:

    public ListNode plusOne(ListNode head) {
        ListNode rd = reverse(head);
        int carry = 1;
        ListNode node = rd.next, tail = null;
        while (node != null) {
            tail = node;
            int sum = node.val + carry;
            node.val = sum % 10;
            carry = sum / 10;
            if (carry == 0)
                break;
            node = node.next;
        }
        if (carry > 0)
            tail.next = new ListNode(carry);
        return reverse(rd.next).next;
    }
    
    private ListNode reverse(ListNode head) {
        ListNode rd = new ListNode(0), node = head;
        while (node != null) {
            ListNode next = node.next;
            node.next = rd.next;
            rd.next = node;
            node = next;
        }
        return rd;
    }
    

    Solution II:

    public ListNode plusOne(ListNode head) {
        ListNode node = head, right = null;
        while (node != null) {
            if (node.val != 9)
                right = node;
            node = node.next;
        }
        if (right == null) {
            right = new ListNode(0);
            right.next = head;
            head = right;
        }
        right.val = right.val + 1;
        node = right.next;
        while (node != null) {
            node.val = 0;
            node = node.next;
        }
        return head;
    }

Log in to reply
 

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