题解 | 链表相加(二)

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) {
        Stack<ListNode> add1 = new Stack<>();
        Stack<ListNode> add2 = new Stack<>();
        while (head1 != null) {
            add1.push(head1);
            head1 = head1.next;
        }
        while (head2 != null) {
            add2.push(head2);
            head2 = head2.next;
        }
        int size = Math.max(add1.size(), add2.size());
        int prev = 0;
        Stack<ListNode> resultStack = new Stack<>();
        for (int i = 0; i < size; i++) {
            int a = add1.isEmpty() ? 0 : add1.pop().val;
            int b = add2.isEmpty() ? 0 : add2.pop().val;
            int sum = a + b + prev;
            int result = 0;
            if (sum >= 10) {
                result = sum - 10;
                prev = 1;
            } else  {
                result = sum;
                prev = 0;
            }
            resultStack.push(new ListNode(result));

        }
        if (prev == 1) {
            resultStack.push(new ListNode(1));
        }
        ListNode resultNode = null;
        ListNode current = null;
        while (!resultStack.isEmpty()) {
            if (resultNode == null) {
                resultNode = resultStack.pop();
                current = resultNode;
            } else {
                current.next = resultStack.pop();
                current = current.next;
            }
        }
        return resultNode;
    }
}

按位加的思路非常直接，但是这里有个问题就是他要从链表的尾巴往前加，这个时候就需要借助堆栈来实现元素的弹出和弹入。

另外就是在最高位为1的时候，需要补上，否则会出现bug

还有需要注意的是，使用prev来记录进位。

但是这个空间复杂度是O(n) ？ 不确定