Leetcode #369. Plus One Linked List

[yokostan]

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode plusOne(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode i = dummy;
        ListNode j = dummy;

        while (j.next != null) {
            j = j.next;       
            if (j.val != 9) {
                i = j;
            }
        }

        if (j.val != 9) {
            j.val++;
        }
        else {
            i.val++;
            i = i.next;
            while (i != null) {
                i.val = 0;
                i = i.next;
            }
        }

        if (dummy.val == 0) 
            return dummy.next;

        return dummy;
    }
}

dummy node is one position ahead of the head with 0 as its value, so we are able to either return 1000 or 899 according to whether head value has been carried or not.

[yokostan]

Stack solution only 12% faster:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode plusOne(ListNode head) {
        ListNode p = head;
        Stack<ListNode> stk = new Stack<>();
        while (p != null){
            stk.push(p);
            p = p.next;
        }
        while (!stk.isEmpty()){
            ListNode cur = stk.pop();
            if (cur.val != 9){
                cur.val = cur.val + 1;
                return head;
            }
            cur.val = 0;
        }
        ListNode newHead = new ListNode(1);
        newHead.next = head;
        return newHead;
    }
}