题解 | #链表相加(二)#

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 || head2 == null) {
            return head1 == null ? head2 : head1;
        }
        Stack<ListNode> stack1 = new Stack<>();
        Stack<ListNode> stack2 = new Stack<>();
        ListNode cur1 = head1;
        ListNode cur2 = head2;
        while (cur1 != null) {
            stack1.push(cur1);
            cur1 = cur1.next;
        }
        while (cur2 != null) {
            stack2.push(cur2);
            cur2 = cur2.next;
        }
        
        cur1 = stack1.pop();
        cur2 = stack2.pop();
        
        int carry = (cur1.val + cur2.val) / 10;
        int val = (cur1.val + cur2.val) % 10;
        ListNode head = new ListNode(val);
        while (!stack1.isEmpty() || !stack2.isEmpty()) {
            val = carry;
            if (!stack1.isEmpty()) {
                val += stack1.pop().val;
            }
            if (!stack2.isEmpty()) {
                val += stack2.pop().val;
            }
            carry = val / 10;
            val = val % 10;
            ListNode cur = new ListNode(val);
            cur.next = head;
            head = cur;
        }
        if (carry != 0) {
            ListNode cur = new ListNode(carry);
            cur.next = head;
            head = cur;
        }
        return head;
    }
    
}