题解 | #给单链表加一#

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类
     * @return ListNode类
     */
    public ListNode plusOne (ListNode head) {
        // write code here

        ArrayDeque<ListNode> stack = new ArrayDeque<>();
        ListNode temp = head;

        while (temp != null) {
            stack.offerFirst(temp);
            temp = temp.next;
        }

        boolean isAddBit = true;
        while (!stack.isEmpty()) {
            temp = stack.removeFirst();
            if (isAddBit) {
                if (temp.val == 9) {
                    isAddBit = true;
                    temp.val = 0;
                } else {
                    isAddBit = false;
                    temp.val = temp.val + 1;
                    break;
                }
            } else {
                break;
            }
        }

        if (isAddBit) {
            temp = new ListNode(1);
            temp.next = head;
            head = temp;
        }


        return head;
    }

}