List两数相加

首先我们先简述一下这个题目：
有两个非空单链表，现在要做十进制加法，将两个链表相加，低位放在个位在链表的头部，如果相加大于9，就要向前面一个进位，大致可以表示成下图

这个时候就要思考如何进位。
在学习汇编语言和计算机组成原理的时候想必大家都听说过一个标志位叫进位标志位CF，或者你没有学过也知道在小学算加法的时候会有进位标识，那进位我们只要加一个进位标识就好.
一般的进位大家都不会加错，但是在最后一个进位的时候就会忘记加，是这个程序里需要特别注意的一点
代码如下

class Solution {public ListNode addTwoNumbers(ListNode l1, ListNode l2) {ListNode head = null;ListNode tail = null;//进位标志int carry = 0;int num1;int num2;while(l1 != null || l2 != null){/*这一段可以优化成num1 = l1 != null ? l1.val : 0;num2 = l2 != null ? l2.val : 0;*/if(l1 == null){num1 = 0;}else{num1 = l1.val;}if(l2 == null){num2 = 0;}else{num2 = l2.val;}int sum = num1 + num2 + carry;if(head == null){head = tail = new ListNode(sum % 10);}else{tail.next = new ListNode(sum % 10);tail = tail.next;}carry = sum/10;if(l1 != null){l1 = l1.next;}if(l2 != null){l2 = l2.next;}}//这里是处理最后一位进位的if(carry > 0){tail.next = new ListNode(carry);}return head;}
}

这题最重要的是链表的顺序和上面的是相反的，就是高位存在链表的首位，最终的方法是差不多的
首先考虑到了用栈,大致的思维图如下图所示：

就是队列先放到栈里，然后再相加入栈，再从栈里出来变成队列，这里就充分使用了栈的先进后出出的特征

class Solution {public ListNode addTwoNumbers(ListNode l1, ListNode l2) {ListNode head = null, tail = null;int carry = 0;Stack<Integer> stackL1 = new Stack();Stack<Integer> stackL2 = new Stack();Stack<Integer> stack = new Stack();while(l1 != null){stackL1.push(l1.val);l1 = l1.next;}while(l2 != null){stackL2.push(l2.val);l2 = l2.next;}while(!stackL1.isEmpty() || !stackL2.isEmpty()){int num1 = !stackL1.isEmpty() ? stackL1.pop() : 0;int num2 = !stackL2.isEmpty() ? stackL2.pop() : 0;int sum = num1 + num2 + carry;stack.push(sum % 10);carry = sum / 10;}if(carry > 0){stack.push(carry);}while(!stack.isEmpty()){if(head == null){head = tail = new ListNode(stack.pop());}else{tail.next = new ListNode(stack.pop());tail = tail.next;}}return head;}
}

很显然这样做是很浪费空间的，而且很多循环，时间也很久。

然后我在题解区看到了一个更加明智的做法
那就相加的数直接变成链表，而不入栈再出栈，同时使用迭代的方式将链表反转
下面是链表反转的代码

ListNode tail = new ListNode(sum);tail.next = head;head = tail;

基本思维的图解是

接下里就是优化的代码：

class Solution {public ListNode addTwoNumbers(ListNode l1, ListNode l2) {ListNode head = null;int carry = 0;Stack<Integer> stackL1 = new Stack();Stack<Integer> stackL2 = new Stack();while(l1 != null){stackL1.push(l1.val);l1 = l1.next;}while(l2 != null){stackL2.push(l2.val);l2 = l2.next;}while(!stackL1.isEmpty() || !stackL2.isEmpty() || carry != 0){int num1 = !stackL1.isEmpty() ? stackL1.pop() : 0;int num2 = !stackL2.isEmpty() ? stackL2.pop() : 0;int sum = num1 + num2 + carry;ListNode tail = new ListNode(sum % 10);tail.next = head;head = tail;carry = sum / 10;}return head;}
}