题目描述：
给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例：
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4) 输出：7 -> 0 -> 8 原因：342 + 465 = 807
题目难度：中等
分析：
属于链表题目的常规操作，并且题目原型已经给了链表部分的代码。这里要注意的是head是个位数，这样从head开始遍历的时候逐步相加就可以了，无疑简化了题目，只需要遍历两个链表，然后注意超过10以后进位就可以了。代码如下：
java:
/** * 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) { // 首先定义一个结果链表作为最后的返回值 ListNode res = new ListNode(0); // 定义p，q分别指向l1，l2 ListNode p = l1, q = l2, curr = res; // 进位标识，初始化为0 int carry = 0; // 遍历链表 while (p != null || q != null) { int x = p != null ? p.val : 0; int y = q != null ? q.val : 0; // 当前值 = 进位 + 两个链表的值 int sum = carry + x + y; // 因为超过10进位，所以 / 10 就可以知道下一次进位是多少了 carry = sum / 10; // 把sum取余得到具体数字并加入当前链表中（比如15 % 10 = 5，因此写5进1） curr.next = new ListNode(sum % 10); // 指向下一位 curr = curr.next; if (p != null) p = p.next; if (q != null) q = q.next; } if (carry > 0) { // 当循环完以后如果进位大于0说明还需要添加一位 curr.next = new ListNode(carry); } // 最后返回链表 return res.next; } }
python:
# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode: res = ListNode(0) p, q, curr, carry = l1, l2, res, 0 while p != None or q != None: x = p.val if p != None else 0 y = q.val if q != None else 0 temp = x + y + carry carry = temp // 10 curr.next = ListNode(temp % 10) if p != None: p = p.next if q != None: q = q.next curr = curr.next if carry > 0: curr.next = ListNode(carry) return res.next
总结：
可以看出不管是java还是python思路都一样，语言只是工具。时间复杂度为O(max(m,n))， 因为遍历链表的时候，可能长短不一样，所以需要遍历的次数应该以长的为准。最后leetcode给出了一个扩展：就是顺序颠倒过来，如下：
(3→4→2)+(4→6→5)=8→0→7
这样的话难度会稍微大点，感兴趣的同学可以尝试下。
