题解 | #两个链表生成相加链表#利用栈实现

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) {
        // write code here
        //借助栈来实现
        if(head1 == null){
            return head2;
        }
        if(head2 == null){
            return head1;
        }
        Stack<ListNode> s1 = new Stack();
        Stack<ListNode> s2 = new Stack();
        Stack<ListNode> res = new Stack();
        while(head1 != null){
            s1.push(head1);
            head1 = head1.next;
        }
        while(head2 != null){
            s2.push(head2);
            head2 = head2.next;
        }
        //依次出栈并相加 放入res
        boolean isNeedAddOne = false;
        while(!s1.isEmpty() || !s2.isEmpty()){
            int n1 = 0;
            int n2 = 0;
            ListNode cur = null;
            if(!s1.isEmpty()){
                cur = s1.pop();
                n1 = cur.val;
            }
            if(!s2.isEmpty()){
                cur = s2.pop();
                n2 = cur.val;
            }
            int sum = n1 + n2;
            if(isNeedAddOne){
                sum += 1;
            }
            if(sum >= 10){
                isNeedAddOne = true;
                int ge = sum % 10;
                cur.val = ge;
            } else {
                isNeedAddOne = false;
                cur.val = sum;
            }
            res.push(cur);
        }
        if(isNeedAddOne){
             ListNode last = new ListNode(1);
             res.push(last);
        }
        ListNode head = res.pop();
        ListNode result = head;
        while(!res.isEmpty()){
            result.next = res.pop();
            result = result.next;
        }
        return head;
    }
}