两个链表相加生成相加链表

两个链表相加生成相加链表
这道题总是报超时，一样的结题思路以及方法，但是总是无法AC，一直75%，报超时（可能太菜代码优化不够）。但总体思路没得问题的。

第一种解法

因为两个数相加的话，无法直接判断是否有进位以及位数是否相等，所以只能从个位向前相加，所以这个刚好符合栈的特性。所以创建两个栈来接收两个链表。
从后向前相加的数学逻辑：定义一个数 carry 用来计数进位之后的数（初始为0），之后每次在循环体内进行赋值为 sum / 10，定义 num1，num2,来接收每次出栈的元素，定义 sum 等于 num1 + num2 + carry（重点：carry 初始为0，每轮循环内对 carry 进行赋值除为 sum / 10，如果进位的话则取值为1，刚好可以用来下一轮循环相加，如果没有进位的话取值为0，相当于没有进位，没有相加），定义 num 为 sum % 10，用来记录每轮循环两个数相加的各位。
最后随着循环创建 ListNode node = new ListNode(num)，然后在循环体外创建一个链表 node2 用来指向 node，然后同时定义一个链表 result 用来指向 node2。

最后反转链表即可。

代码优化地方：可以在循环体内每次创建新的链表的时候，直接在接收的时候让链表反向指向，从而使最后生成的链表就是最后的结果，不用最后反转链表。
代码如下：

```
public ListNode addInList (ListNode head1, ListNode head2) {

 // write code here
 //定义两个栈，用来存放两个链表的元素，刚好其结构特性符合相加的步骤
 Stack<Integer> stack1 = new Stack<>();
 Stack<Integer> stack2 = new Stack<>();
 //往栈里面添加元素
 ListNode node1 = head1;
 ListNode node2 = head2;
 while (node1 != null) {
     stack1.add(node1.val);
     node1 = node1.next;
 }
 while (node2 != null) {
     stack2.add(node2.val);
     node2 = node2.next;
 }
 //开始相加
 int carry = 0;
 ListNode node = new ListNode(0);
 ListNode result = node;
 while(!stack1.empty() || !stack2.empty() || carry != 0) {
     int a = 0;
     int b = 0;
     if (!stack1.empty()) {
         a = stack1.peek();
         stack1.pop();
     }
     if (! stack2.empty()) {
         b = stack2.peek();
         stack2.pop();
     }
     int sum = a + b + carry;
     int num = sum % 10;
     carry  = sum / 10;
     ListNode nodeNum = new ListNode(num);
     node.next = nodeNum;
     node = node.next;
 }
 result = result.next;
 ListNode pre = result;
 ListNode next = null;
 while (result !=null) {
     pre = result.next;
     result.next = next;
     next = result;
     result = pre;
 }
 return next;

第二种思路
不仁不义法。在整体解法：疯狂转换。

创建两个 list1，list2 来接收两个链表，然后直接转 String，转Integer，然后直接相加，然后将相加的结果直接转String，然后最后截止创建链表接收。
但是内存开销有点大，属于可以结题的一种思路。