题解 | #两个链表生成相加链表#

	链表相加方式为从两个表尾逐级相加，十位向上一节点进位。用栈可以完美解决此问题。



	用两个栈q1、q2分别保存两个链表的值，从头到尾将链表值压入栈中。那么，两个参数链表尾的数必然压入了栈头部，依次从栈中取数后刚好可以从表尾进行相加。再用一个栈q3存储结果链表的各节点的值，从保存输入参数的两个栈中依次取值相加，并加上上一次相加后的进位值，将结果的个位数压入q3中，进位值更新为结果的十位数值。最后将q3中的值依次抛出写入到结果链表中。

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param head1 ListNode类 
     * @param head2 ListNode类 
     * @return ListNode类
     */
    public ListNode addInList (ListNode head1, ListNode head2) {
        if (head1 == null)
			return head2;
		if (head2 == null) {
			return head1;
		}
		Stack<Integer> q1 = new Stack<Integer>();
		Stack<Integer> q2 = new Stack<Integer>();
		Stack<Integer> q3 = new Stack<Integer>();
		int up_bit = 0;//进位值
		while(head1!=null) {
			q1.push(head1.val);
			head1=head1.next;
		}
		while(head2!=null) {
			q2.push(head2.val);
			head2=head2.next;
		}
		
		while(!(q1.isEmpty()&&q2.isEmpty())) {
			int i1 = 0;
			int i2 = 0;
			if(!q1.isEmpty()) {
				i1 = q1.pop();
			}
			if(!q2.isEmpty()) {
				i2 = q2.pop();
			}
			int tot = i1+i2+up_bit;
			q3.push(tot%10);
			up_bit=tot/10;		
		}
		if(up_bit>0) {
			q3.push(up_bit);
		}
		ListNode n = new ListNode(0);
		ListNode r = n;
		while(!q3.isEmpty()) {
			n.val=q3.pop();
			if(!q3.isEmpty()) {
				ListNode nn = new ListNode(0);
				n.next=nn;
				n = n.next;
			}
		}
		return r;
    }
}