PlusOneLinkedListOPT [source code]

public class PlusOneLinkedListOPT {
static
/******************************************************************************/
public class Solution {
    public ListNode plusOne(ListNode head) {
        if (head == null)
            return new ListNode(1);
        ListNode plused = plusOne(head.next);
        if (plused != head.next)
            head.val++;
        if (head.val <= 9)
            return head;
        head.val = 0;
        plused.next = head;
        return plused;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        PlusOneLinkedListOPT.Solution tester = new PlusOneLinkedListOPT.Solution();
        int[][] inputs = {
            {1,2,3}, {1,2,4},
            {9}, {1,0},
            {8,9,9,9}, {9,0,0,0},
            {1,9}, {2,0},
        };
        for (int i = 0; i < inputs.length / 2; i++) {
            ListNode head = ListNode.buildListNode(inputs[2 * i]);
            ListNode answer = ListNode.buildListNode(inputs[1 + 2 * i]);
            System.out.println(Printer.separator ());
            String inputStr = Printer.listNode(head);
            String outputStr = Printer.listNode(tester.plusOne(head));
            String answerStr = Printer.listNode(answer);
            System.out.println(Printer.wrapColor(inputStr, "magenta") + " -> " + outputStr + Printer.wrapColor(", expected: " + answerStr, outputStr.equals(answerStr) ? "green" : "red"));
            String headStr = Printer.listNode(head);
            System.out.println(Printer.wrapColor("Original input: " + headStr, headStr.equals(outputStr) ? "green" : "red"));
        }
    }
}

这个是stefan写的没有helper的recursion版本;

If the +1 was already handled without further carry, then the result is the given head node. Otherwise it's a new node (with carry value 1). In other words, a carry-node is created at the end and gets carried towards the front until it has been fully integrated.

看了半天, 就算用简单举例还是有点不理解, 最后干脆就直接打印log来看, 才算是看懂了; 关键的例子是8,9,9,9这个例子;

他这里这个carry node实际上就是一开始最底下level的那个null产生的这个1node. 这个1node然后一步一步的作为其他向上的level的carry node. 在这个过程中, input的head这个list本身的结构其实是没有被修改的, 唯一在不停变化的只有:

• 某些node的value
• 最后这个carry node的next.

这个算法非常的聪明; 首先这里的返回值是node, 所以在上一层判断的其实就是下一层返回上来的node是否是一个carry node(如果是carry node, 那么就跟上一层head原来的next不相同了: 注意这里是用==判断, 判断的是reference). 当上层head如果在看到自己的next已经变成了一个carry node的时候, 自己同时也要产生carry的时候, 不是自己重新制造一个carry node, 而是直接把下层的carry node作为自己的carry node就行了, 并且把这个carry node返回给自己的上一层: 但是在这个过程中, 整个list本身的结构一点都没有发生变化;

Problem 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
Difficulty:Medium
Total Accepted:15.4K
Total Submissions:28.3K
Contributor: LeetCode
Companies
google
Related Topics
linked list
Similar Questions
Plus One