本文共 1647 字，大约阅读时间需要 5 分钟。

leetcode-两数相加

给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。 如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。 您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例：

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4) 输出：7 -> 0 -> 8 原因：342 + 465 = 807

实现思路：

1.我们先看数据结构，ListNode 含有一个数值部分int，和一个指向同类节点对象的指针 2.两数相加，首先输入的数据是逆向输入的，先输入各位，依次十位百位等，当我们进行相加的时候，我们首先要创建一个新的链表结构来存储结果 这个链表的头节点是pre，然后设置一个游标cur表示进行下一步加和的结果的节点，因为两个不超过十的数进行相加，结果只能在0–19之间，所以我们还需要设置一个进位的标志carry，当两个节点的val值相加后，对十取余为cur节点的val,进位标志carry的值应为对10相除取整 3.然后将节点后移，两个相加的链表有一个为null则将其val设为0，将另一个链表val和进位carry相加，当l1,l2均为为null停止，还要注意最后carry的值的情况，不要遗忘 代码展视：

/** * 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 pre = new ListNode(0);        ListNode cur = pre;        int carry = 0;        while(l1 != null || l2 != null) {               int x = l1 == null ? 0 : l1.val;            int y = l2 == null ? 0 : l2.val;            int sum = x + y + carry;                        carry = sum / 10;            sum = sum % 10;            cur.next = new ListNode(sum);            cur = cur.next;            if(l1 != null)                l1 = l1.next;            if(l2 != null)                l2 = l2.next;        }        if(carry == 1) {               cur.next = new ListNode(carry);        }        return pre.next;    }}

复杂度分析

时间复杂度：O(max(m,n))，其中 m,nm,n 为两个链表的长度。我们要遍历两个链表的全部位置，而处理每个位置只需要 O(1) 的时间。 空间复杂度：O(max(m,n))。答案链表的长度最多为较长链表的长度 +1。