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

用java语言也能通过，但是运行时间耗费2.7s。

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
        Deque<Integer> s1 = new ArrayDeque<>();
        Deque<Integer> s2 = new ArrayDeque<>();

        pushStack(head1,s1);
        pushStack(head2,s2);

        int c = 0;//进位
        ListNode r = null; //结果列表
        while (!s1.isEmpty() || !s2.isEmpty()){

            int a = !s1.isEmpty() ? s1.pop() : 0;
            int b = !s2.isEmpty() ? s2.pop() : 0;

            int sum = a + b + c;

            c = sum / 10;

            ListNode node = new ListNode(0);
            node.val = sum % 10;
            
            //头插法
            node.next = r;
            r = node;
        }
        if (c != 0){
            ListNode node = new ListNode(0);
            node.val = c;

            //头插法
            node.next = r;
            r = node;
        }

        return r;
    }
    
    private void pushStack(final ListNode l, Deque<Integer> s) {
        ListNode curr = l;
        while (curr != null){
            s.push(curr.val);
            curr = curr.next;
        }

    }
}