[LintCode] Problem 904 - Plus One Linked List

Posted on | In ,

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

No.1

Input: 1 -> 2 -> 3 -> null

Output: 1 -> 2 -> 4 -> null

Explanation:
123 + 1 = 124

No.2

Input: 9 -> 9 -> null

Output: 1 -> 0 -> 0 -> null

Explanation:
99 + 1 = 100

Code

1
2
3
4
5
6
7
8
public class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
        next = null;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public ListNode plusOne(ListNode head) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode slow = dummy;
    ListNode fast = dummy;

    while (fast.next != null) {
        fast = fast.next;

        if (fast.val != 9)
            slow = fast;
    }

    if (fast.val != 9) {
        fast.val++;
    }
    else {
        slow.val++;
        slow = slow.next;

        while (slow != null) {
            slow.val = 0;
            slow = slow.next;
        }
    }

    return dummy.val == 0 ? head : dummy;
}