369. Plus One Linked List

https://leetcode.com/problems/plus-one-linked-list/description/

Given a non-negative integer represented as non-empty a singly linked list of digits, plus one to the integer.

You may assume the integer do not contain any leading zero, except the number 0 itself.

The digits are stored such that the most significant digit is at the head of the list.

Example :

Input: [1,2,3]
Output: [1,2,4]

Thoughts

由linked list表示一个正整数，每个node表示一个数字，最大的位在head，实现对它+1的效果。从右数第一个不为9的+1，它右边的全部置为0。找右边第一个不为9的用先后两个指针。

Code

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def plusOne(self, head: ListNode) -> ListNode:
        i, j = None, head
        while j:
            if j.val != 9:
                i = j
            j = j.next
        if not i:
            new_h = ListNode(1)
            new_h.next = head
            i = head
            head = new_h
        else:
            i.val += 1
            i = i.next
        while i:
            i.val = 0
            i = i.next
        return head  
            

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode plusOne(ListNode head) {
        Stack<ListNode> stack = new Stack<>();
        ListNode dummy = new ListNode(0), node = dummy, lastNotNine = dummy;
        dummy.next = head;
        while (node.next != null) {
            if (node.val != 9) {
                lastNotNine = node;
            }
            node = node.next;
        }
        if (node.val != 9) {
            node.val++;
        } else {
            lastNotNine.val++;
            node = lastNotNine.next;
            while (node != null) {
                node.val = 0;
                node = node.next;
            }
        }

        if (dummy.val != 0) {
            return dummy;
        } else {
            return dummy.next;
        }
    }
}

Analysis

时间复杂度O(N).