题目
??给定两个非空链表，表示两个非负的整数，其每位数字都是按照 逆序 的方式存储，并且每个节点只能存储一位数字。
??将两个数相加，并以相同方式返回一个表示和的链表。
??假设除了数字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]
思路
??由于输入的两个链表都是 逆序 存储数字的位数的，因此两个链表中同一位置的数字可以直接相加。
??此时同时遍历两个链表，逐位计算它们的和，并与当前位置的进位值相加。具体而言，如果当前两个链表处相应位置的数字为n1,n2,进位值为carry,则它们的和为n1+n2+carry；其中，结果链表处相应位置的数字为*(n1+n2+carry)%10*,而新的进位值为*(n1+n2+carry)/10*.
??如果两个链表的长度不同，则可以认为长度短的链表的后面有若干个0.
??此外，如果链表遍历结束后，有carry>0,还需要在答案链表的后面附加一个节点，节点的值为carry；
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode head = null, tail = null;
int carry = 0;
while (l1 != null || l2 != null) {
int n1 = l1 != null ? l1.val : 0;
int n2 = l2 != null ? l2.val : 0;
int sum = n1 + n2 + 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;
}
}
复杂度分析：
- 时间复杂度：O(max(m,n)),其中m和n分别为两个链表的长度，要遍历两个链表的全部位置，而处理每个位置只需要O(1)的时间
- 空间复杂度: O(1).注意返回值不计入空间复杂度。
Java代码
public class Test_3 {
public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode pre = new ListNode(0);
ListNode cur= pre;
int carray =0;
while (l1!=null||l2!=null){
// 取l1的值，有取，无默认0
int x = l1==null?0:l1.val;
// 取l2的值，有取，无默认0
int y = l2==null?0:l2.val;
//计算l1+l2+进位
int sum = x+y+carray;
//是否需要进位
carray = sum/10;
//取余后为当前位置的值
sum = sum%10;
//将当前位置的值关联到当前节点的下一个节点
cur.next = new ListNode(sum);
//开始处理下一位
cur = cur.next;
//l1取下一位
if (l1!=null){
l1 = l1.next;
}
//l2取下一位
if (l2!=null){
l2 = l2.next;
}
}
//进位为1需要新增一个节点
if (carray==1){
cur.next = new ListNode(carray);
}
return pre.next;
}
public static class ListNode {
int val;
ListNode next;
ListNode() {}
ListNode(int val) { this.val = val; }
ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
public static void main(String[] args) {
ListNode l1 = new ListNode(9);
ListNode l11 = new ListNode(9);
ListNode l12 = new ListNode(9);
ListNode l14 = new ListNode(9);
ListNode l15 = new ListNode(9);
ListNode l16 = new ListNode(9);
ListNode l17 = new ListNode(9);
l1.next=l11;l11.next=l12;l12.next=l14;l14.next=l15;l15.next=l16;l16.next=l17;
ListNode l2 = new ListNode(9);
ListNode l21 = new ListNode(9);
ListNode l22 = new ListNode(9);
ListNode l23 = new ListNode(9);
l2.next=l21;l21.next=l22;l22.next=l23;
ListNode listNode = addTwoNumbers(l1,l2);
while (listNode!=null){
System.out.println(listNode.val);
listNode = listNode.next;
}
}
}