描述

假设链表中每一个节点的值都在 0 - 9 之间，那么链表整体就可以代表一个整数。 给定两个这种链表，请生成代表两个整数相加值的结果链表。

 

答案：栈

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