题目描述：
给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。 你可以假设除了数字 0 之外，这两个数字都不会以零开头。
进阶：
如果输入链表不能修改该如何处理？换句话说，你不能对列表中的节点进行翻转。
示例：
输入：(7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4) 输出：7 -> 8 -> 0 -> 7
分析：
比较简单的办法就是遍历两个链表，然后生成两个整数，再把两个整数相加，最后再把整数拆分成链表。但是这样的话如果链表长度很长就会整数溢出或者超出时间限制。因为此题是单向链表，并且需要把尾部当作低位来相加，就是逆序，所以可以用栈（Stack）来做，因为栈是先进后出，符合此题要求。
代码如下：
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 = null; Stack<Integer> s1 = new Stack<>(); Stack<Integer> s2 = new Stack<>(); // 遍历链表，把值压栈 while (l1 != null) { s1.push(l1.val); l1 = l1.next; } while (l2 != null) { s2.push(l2.val); l2 = l2.next; } int carry = 0; while (!s1.isEmpty() || !s2.isEmpty() || carry > 0) { // 由于栈是FILO（先进后出）所以每次弹栈都是从低位->高位 int sum = (s1.isEmpty() ? 0 : s1.pop()) + (s2.isEmpty() ? 0 : s2.pop()) + carry; ListNode temp = new ListNode(sum % 10); carry = sum / 10; // 链表的头插法 temp.next = res; res = temp; } return res; } }
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: s1, s2, res = [], [], None while l1: s1.append(l1.val) l1 = l1.next while l2: s2.append(l2.val) l2 = l2.next carry = 0 while s1 or s2 or carry > 0: sum = (0 if not s1 else s1.pop()) + (0 if not s2 else s2.pop()) + carry temp = ListNode(sum % 10) temp.next = res res = temp carry = sum // 10 return res
总结：
链表的常规题目，需要了解栈以及链表的头插法、尾插法。
