Very simple Java O(n) time O(1) space solution.


  • 1
    D

    The idea is very simple. We go through the list from head and find the last node whose value is not 9. After one scan, we find the node whose value is not 9, plus 1 to the value of this node. Then go through the nodes after this node to the end and set 0 at mean time.

    A little bit tricky but very easy to implement and straight forward.

    public class Solution {
    public ListNode plusOne(ListNode head) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode notNine = dummy;
    ListNode p = head;
    while (p != null) {
    if (p.val != 9) {
    notNine = p;
    }
    p = p.next;
    }
    notNine.val = notNine.val + 1;
    notNine = notNine.next;
    while (notNine != null) {
    notNine.val = 0;
    notNine = notNine.next;
    }

        return dummy.val > 0 ? dummy : dummy.next;
    }
    

    }


Log in to reply
 

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