原文链接：https://blog.csdn.net/qq_39355828/article/details/120447768 (opens new window) 剑指 Offer II 025. 链表中的两数相加

给定两个 非空链表 l1和 l2 来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。

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

示例1：

输入：l1 = [7,2,4,3], l2 = [5,6,4]

输出：[7,8,0,7]

示例2：

输入：l1 = [2,4,3], l2 = [5,6,4]

输出：[8,0,7]

示例3：

输入：l1 = [0], l2 = [0]

输出：[0]

两个链表之所以不能直接相加，也不能和数组一样逆序，最关键在于链表的单向，因此，借助两个栈对链表进行逆序。需要注意的是最后的近卫处理，以及当一个链表为空的时候怎样解决问题。代码来自评论区

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
     Stack<Integer>st1=new Stack<Integer>();
     Stack<Integer>st2=new Stack<Integer>();
     while(l1!=null)
     {
         st1.push(l1.val);
         l1=l1.next;
     }
     while(l2!=null)
     {
         st2.push(l2.val);
         l2=l2.next;
     }
     int carry=0;
     ListNode head=null;
     while(!st1.isEmpty()||!st2.isEmpty()||carry>0)
     {   //将两个值以及进位加起来
         int sum=carry;
         sum=sum+(st1.isEmpty()?0:st1.pop());
         sum=sum+(st2.isEmpty()?0:st2.pop());
         //产生新的节点
         ListNode node=new ListNode(sum%10);
         //将当前节点的下一个指向头节点
         node.next=head;
         //头指针向前移动，完成节点的添加
         head=node;
         carry=sum/10;
     }
     return head;
    }