题解 | #链表相加(二)#栈/反转链表后相加

解法1:栈

用2个栈来存储链表1和2，链表3来表示加和的结果，一个临时变量保存进位carryOver

需要注意的点是：当某个链表的长度较长的时候，将它放入结果是，也要记得处理carryOver的部分

时间复杂度：O(m + n)

空间复杂度：O(m + n)

import java.util.*;
public class Solution {
    public ListNode addInList (ListNode head1, ListNode head2) {
        if (head1 == null) {
            return head2;
        }

        if (head2 == null) {
            return head1;
        }
        
        Stack<ListNode> stack1 = putNodesIntoStack(head1);
        Stack<ListNode> stack2 = putNodesIntoStack(head2);
        Stack<ListNode> result = new Stack<ListNode>();
        int carryOver = 0;
        while (!stack1.empty() || !stack2.empty()) {
            int total = carryOver;
            if (!stack1.empty()) {
                total += stack1.pop().val;
            }
            if (!stack2.empty()) {
                total += stack2.pop().val;
            }
            carryOver = total / 10;
            ListNode currentNode = new ListNode(total % 10);
            result.push(currentNode);
        }

        if (carryOver != 0) {
            result.push(new ListNode(carryOver));
        }
        return buildLinkedListByStack(result);
    }

    private Stack<ListNode> putNodesIntoStack(ListNode head) {
        ListNode pointer = head;
        Stack<ListNode> stack = new Stack<ListNode>();
        while (pointer != null) {
            stack.push(pointer);
            pointer = pointer.next;
        }
        return stack;
    }

    private ListNode buildLinkedListByStack(Stack<ListNode> stack) {
        if (stack == null || stack.empty()) {
            return null;
        }
        ListNode head = stack.pop();
        ListNode currentNode = head;
        ListNode nextNode;
        while (!stack.empty()) {
            nextNode = stack.pop();
            currentNode.next = nextNode;
            nextNode.next = null;
            currentNode = nextNode;
        }
        return head;
    }
}

解法2:反转链表后相加

栈只是起到一个反转的效果，如果不想要栈，直接反转后做加法也是可以的

要注意的是，反转后做加法得到的结果也要反转一次，需要采用前驱插入法

时间复杂度：O(m + n)

空间复杂度：O(1)

import java.util.*;
public class Solution {
    public ListNode addInList (ListNode head1, ListNode head2) {
        if (head1 == null) {
            return head2;
        }

        if (head2 == null) {
            return head1;
        }

        ListNode reverse1 = reverseLinkedList(head1);
        ListNode reverse2 = reverseLinkedList(head2);
        int total = 0;
        int carryOver = 0;
        ListNode current = null;
        ListNode prev = null;
        while (reverse1 != null || reverse2 != null || carryOver != 0) {
            total = carryOver;
            if (reverse1 != null) {
                total += reverse1.val;
                reverse1 = reverse1.next;
            }
            if (reverse2 != null) {
                total += reverse2.val;
                reverse2 = reverse2.next;
            }
            carryOver = total / 10;
            prev = new ListNode(total % 10);
            prev.next = current;
            current = prev;
        }
        return current;
    }

    private ListNode reverseLinkedList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode headOfReversedList = reverseLinkedList(head.next);
        head.next.next = head;
        head.next = null;
        return headOfReversedList;
    }

}