本文正在参加「Java主题月 – Java 刷题打卡」，详情查看活动链接

一、题目描述

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

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

你可以假设除了数字 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
题目数据保证列表表示的数字不含前导零

二、思路分析

题目解读

这是一道两数相加的题目，并把两数分别存放到两个不同的链表中，链表中的每一节点存放一位数，并以逆序存放，如：链表 l1: [2,4,3]，则代表数字 342；链表 l2: [5,6,4],则代表数字 465。此时，两数相加得到的输出链表为 [7,0,8] (342 + 465 = 807 )。另：两数相加必须要满足运算规则。

知识点复习

本题中提及到了链表，在此对链表进行复习回顾，更有助于对此题的解答。

和数组相同，链表是一种线性表结构。从底层存储结构上看，链表不需要一整块连续的存储空间，而是通过“指针”将一组零散的内存块串联起来使用。链表中的每个内存块被称为链表的“结点”，每个结点除了要存储数据外，还需要记录上(下)一个结点的地址。

特点：

插入、删除数据效率高，只需要考虑相邻结点的指针改变，不需要搬移数据，时间复杂度是 O(1)。
随机查找效率低，需要根据指针一个结点一个结点的遍历查找，时间复杂度为 O(n)。
与内存相比，链表的空间消耗大，因为每个结点除了要存储数据本身，还要储存上(下)结点的地址。

常用的链表类型:

单链表

循环链表

双向链表

双向循环列表

本题目中用到的是最为简单“单链表”。

算法分析

本题难度：★★★☆☆

本题的关键在于对题目的充分理解，正确读懂题目就离成功不远了。我们只需遍历两个数的链表 l1、l2，逐位计算它们之和 n1 + n2，并需要考虑计算结果是否进位(即：n1 + n2 >10 的结果)。

此外，需对两个链表做一些判断或特殊处理，以防止出现异常或遗漏场景：

两链表必须非空
两链表长度不同时，即两数位数不同，则可认为长度短的链表的后面全是0
……

三、代码实现

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode head = null, tail = null;
        int carry = 0;
        while (null != l1 && null != l2) {
            int num1 = null != l1 ? l1.val : 0;
            int num2 = null != l2 ? l2.val : 0;
            int sum = num1 + num2 + carry;
            if (head == null) {
                head = tail = new ListNode(sum % 10);
            } else {
                tail.next = new ListNode(sum % 10);
                tail = tail.next;
            }
            carry = sum / 10;
            if (l1 != null) {
                l1 = l1.next;
            }
            if (l2 != null) {
                l2 = l2.next;
            }
        }
        if (carry > 0) {
            tail.next = new ListNode(carry);
        }
        return head;
    }
}
复制代码