算法描述

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

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

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

示例：
??两个链表数字：531和742
在这里插入图片描述
??相加结果为：1273
??

算法解答


public class TwoNumPlus {

    public static void main(String[] args) {
        Node one = new Node(1, new Node(2, new Node(3)));
        Node two = new Node(4, new Node(5));
        Node result = new TwoNumPlus().addTwoNumbers(one, two);
        Node tail = result;
        while (result != null) {
            System.out.print(result.val);
            result = result.next;
        }
    }

    public Node addTwoNumbers(Node one, Node two) {
        Node head = null;
        Node tail = null;
        int jinWei = 0;
        while (one != null || two != null) {
            int oneVal = one == null ? 0 : one.val;
            int twoVal = two == null ? 0 : two.val;
            int plusResult = oneVal + twoVal + jinWei;
            jinWei = plusResult / 10; // 求进位，用除法，因为是整数所有
            if (head == null) {
                head = new Node(plusResult % 10);// 进位后剩下的用取模计算
                tail = head;
            } else {
                tail.next = new Node(plusResult % 10);
                tail = tail.next;
            }
            one = one != null ? one.next : null;
            two = two != null ? two.next : null;
        }
        if (jinWei > 0) {
            // 处理最后一个进位
            tail.next = new Node(jinWei);
        }
        return head;
    }


}

Node代码如下：


class Node {
    public Node(int val) {
        this.val = val;
    }

    public Node(int val, Node next) {
        this.val = val;
        this.next = next;
    }

    int val;
    Node next;

    public int getVal() {
        return val;
    }

    public void setVal(int val) {
        this.val = val;
    }

    public Node getNext() {
        return next;
    }

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