LeetCode：两数之和（链表）

题目：

给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

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

示例：

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

来源：力扣（LeetCode）

解：

这道题之前是有做的，而且还需要手动反转链表，这里倒是简化了。

记得当时是减短代码，所以采用了时间O（n），空间O（n）的做法。这里选择时间O（n），空间O（1）的做法，节省点空间，代码复杂了，也算是区别另一道题的解法。

直接用链表1作为结果链表，省去额外辅助空间。注意链表1不是长链表时的切换。

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { if(l1==null){ return l2; } if(l2==null){ return l1; } int cy=0,v; ListNode t1=l1,t2=l2; //两链表都存在，相加 while(t1.next!=null && t2.next!=null){ v=t1.val+t2.val+cy; t1.val=v; cy=v/10; t1=t1.next; t2=t2.next; } v=t1.val+t2.val+cy; t1.val=v; cy=v/10; //确保1为长链表 if(t1.next==null){ t1.next=t2.next; } //单链表进位加 while(cy!=0 && t1.next!=null){ t1=t1.next; v=t1.val+cy; t1.val=v; cy=v/10; } if(cy!=0){ t1.next=new ListNode(1); t1.next.next=null; } return l1; } }