题目: 两数相加

两数相加

难度：中等

给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例 1：

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.

示例 2：

输入：l1 = [0], l2 = [0]
输出：[0]

示例 3：

输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]

提示：

每个链表中的节点数在范围 [1, 100] 内
0 <= Node.val <= 9
题目数据保证列表表示的数字不含前导零

分析

两数相加中两个输入都是以链表形式表示的。

链表存储的形式可以方便的转为十进制的整形，因为链表中每个结点代表某个位上的值，再乘以其位数就可以还原是整形，例如文中的[2, 4, 3]表示的是2+4*10+3*10²，也就是342。

该题先转换为数字在进行计算在数字较小的时候没有问题，但是因为整形的表示范围的问题，如题中所示的100位的数字会出现溢出情况，所以不能转为整型之后计算。

双指针

直接使用链接计算，使用两个指针分别指向链表头部，将指针指向的两个数字相加，将数字的和存入结果链表，如果数字超过10，则将和的个位数存入链表，同时使用一个辅助的整形作为进位的存储，如果和超过10，则将进位存为1，后续操作的时候除了计算两个指针指向的数字之外，还需要加上进位。

两个指针依此右移一位，重复上述过程，如果其中一个链表已经为空，则第一次将另一个链表的结点加上进位进行计算即可。

题解

package 两数相加.双指针;

class LinkNode{
    private int value;
    private LinkNode next;

    public static LinkNode getInstance(int[] nums){
        LinkNode dummyHeader = new LinkNode(0);
        LinkNode current = dummyHeader;
        for(int num : nums){
            LinkNode nextNode = new LinkNode(num);
            current.next = nextNode;
            current = nextNode;
        }

        return dummyHeader;
    }

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

    public int getValue() {
        return value;
    }

    public LinkNode getNext() {
        return next;
    }

    public void setNext(LinkNode next) {
        this.next = next;
    }
}

public class Solution {

    public static LinkNode solute(int[] nums1, int[] nums2) {
        LinkNode numLink1 = LinkNode.getInstance(nums1);
        LinkNode numLink2 = LinkNode.getInstance(nums1);

        boolean hasNext1 = true;
        boolean hasNext2 = true;
        int carry = 0;
        LinkNode header = null;
        LinkNode currentNode = null;
        while (true) {
            LinkNode numLinkNode1;
            LinkNode numLinkNode2;
            int firstNum = 0;
            int secondNum = 0;

            if (hasNext1) {
                numLinkNode1 = numLink1.getNext();
                if (numLinkNode1 == null) {
                    hasNext1 = false;
                } else {
                    firstNum = numLinkNode1.getValue();
                }
            }
            if (hasNext2) {
                numLinkNode2 = numLink2.getNext();
                if (numLinkNode2 == null) {
                    hasNext2 = false;
                } else {
                    secondNum = numLinkNode2.getValue();
                }
            }

            if (!hasNext1 && !hasNext2) {
                break;
            }

            int plus = firstNum + secondNum + carry;
            carry = plus / 10;
            int digit = plus % 10;

            LinkNode linkNode = new LinkNode(digit);
            if (currentNode == null) {
                header = linkNode;
                currentNode = linkNode;
            } else {
                currentNode.setNext(linkNode);
                currentNode = linkNode;
            }
        }
        return header;
    }
}