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

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head1 ListNode类 
     * @param head2 ListNode类 
     * @return ListNode类
     */
    public ListNode addInList (ListNode head1, ListNode head2) {
        // write code here
        Stack<ListNode> s1 = new Stack<>();
        Stack<ListNode> s2 = new Stack<>();
        while(head1 != null){
            s1.push(head1);
            head1 = head1.next;
        }
        while(head2 != null){
            s2.push(head2);
            head2 = head2.next;
        }
        //进位
        int tmp = 0;
        ListNode dummy = new ListNode(-1);
        ListNode head = dummy.next;
        while(!s1.empty() || !s2.empty()){
            int val = tmp;

            //val += s1.pop().val + s2.pop().val;
            if(!s1.empty()){
                val += s1.pop().val;
            }
            if(!s2.empty()){
                val += s2.pop().val;
            }

            ListNode p = new ListNode(val%10);
            tmp = val / 10;
            p.next = head;
            dummy.next = p;
            head = p;
        }
        if(tmp != 0){
            ListNode p = new ListNode(tmp);
            p.next = head;
            dummy.next = p;
        }
        return dummy.next;

    }
}

1. 方法一：辅助栈，先将两个链表元素分别加入对应的栈，然后元素逐个出栈，使用头插法组成新链表，需要注意进位
2. 方法二：反转链表，先将两个链表反转，再逐个相加，最后将新链表反转