Add Two Numbers

要求

有2个非空链表，存储的都是非负整数中的每一位，低位存储在表头方向，高位存储在表尾方向，两个链表都没有前置0，除非这个数本来就是0.
现在要求计算出2个数的值，并且还是用链表存储，还是低位在表头方向，高位在表尾方向。

示例

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

代码用法

public class Main {
    /**
     * 有2个非空链表，存储的都是非负整
     * 数中的每一位，低位存储在表头方向
     * ，高位存储在表尾方向，两个链表都
     * 没有前置0，除非这个数本来就是0.
     * 现在要求计算出2个数的值，并且还是
     * 用链表存储，还是低位在表头方向，
     * 高位在表尾方向。
     * @param args
     */
    public static void main(String[] args) {
    // write your code here
        //首先建立输入链表。
        SingleLinkerNode list0 = AddTwoNumbers.numberToLink(4982);
        SingleLinkerNode list1 = AddTwoNumbers.numberToLink(398465);
        AddTwoNumbers.addTwoLinkers(list0,list1);
        System.out.println(AddTwoNumbers.lingkerToNumber(list0));
    }
}

public class AddTwoNumbers {
    /**
     * 输入一个非负整数，并把它从低位到高位生成链表。
     * 比如说342变成2 -> 4 -> 3
     * @param number
     * @return
     */
    static public SingleLinkerNode numberToLink(int number) {
        int component = number;
        SingleLinkerNode resultHeader = null;
        SingleLinkerNode currentHeader = resultHeader;
        while (component > 0) {
            int bitNumber = component % 10;
            component = component / 10;
            if (resultHeader == null){
                resultHeader = new SingleLinkerNode(bitNumber);
                currentHeader = resultHeader;
            }
            else {
                SingleLinkerNode newNode = new SingleLinkerNode(bitNumber);
                currentHeader.nextPointer = newNode;
                currentHeader = newNode;
            }
        }
        return  resultHeader;
    }

    /**
     * 本算法是要把list1上面的值加到list0上面去。
     * @param list0
     * @param list1
     * @return
     */
    static public SingleLinkerNode addTwoLinkers(SingleLinkerNode list0,SingleLinkerNode list1) {
        SingleLinkerNode list0Pointer = new SingleLinkerNode(-1);
        SingleLinkerNode list1Pointer = new SingleLinkerNode(-1);
        list0Pointer.nextPointer = list0;
        list1Pointer.nextPointer = list1;
        int carry = 0;
        while (list0Pointer.nextPointer != null && list1Pointer.nextPointer != null) {
            int augend = list1Pointer.nextPointer.getValue();
            int addend = list0Pointer.nextPointer.getValue();
            int newBitNumber = augend + addend + carry;
            if (newBitNumber > 9)carry = 1;
            else carry = 0;
            newBitNumber %= 10;
            list0Pointer.nextPointer.setValue(newBitNumber);
            list0Pointer = list0Pointer.nextPointer;
            list1Pointer = list1Pointer.nextPointer;
        }
        if (list1Pointer.nextPointer != null)list0Pointer.nextPointer = list1Pointer.nextPointer;
        while (list0Pointer.nextPointer != null) {
            int newValue = list0Pointer.nextPointer.getValue() + carry;
            if (newValue > 9)carry = 1;
            else carry = 0;
            newValue %= 10;
            list0Pointer.nextPointer.setValue(newValue);
            list0Pointer = list0Pointer.nextPointer;
        }
        if (carry == 1)list0Pointer.nextPointer = new SingleLinkerNode(1);
        return list0;
    }

    /**
     * 链表转换成数字
     * @param header
     * @return
     */
    static public int lingkerToNumber(SingleLinkerNode header) {
        SingleLinkerNode currentPointer = header;
        int result = 0;
        int times = 1;
        while (currentPointer != null) {
            result += currentPointer.getValue() * times;
            times *= 10;
            currentPointer = currentPointer.nextPointer;
        }
        return result;
    }
}

package com.company;

public class SingleLinkerNode {
    public SingleLinkerNode nextPointer = null;
    private int value;

    public SingleLinkerNode(int value) {
        this.value = value;
    }

    public int getValue() {
        return value;
    }

    public void setValue(int value) {
        this.value = value;
    }
}

输出

403447