445. 两数相加 II (opens new window)

1.栈

分析：要保证时间O(max(m+n))且不能翻转链表，显然需要另外的数据结构来辅助整个加法过程。而链表处理进位是一个反序处理的过程，需要先处理低位的加法进位(链表尾节点)，再处理高位，天然符合“先进后出”。

因此使用两个栈分别保存每一个链表节点，每次同步出栈进行加法运算，根据栈的性质不需要考虑位与位之间对齐的问题。

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        Stack<ListNode> stack1=new Stack<>();
        Stack<ListNode> stack2=new Stack<>();
        while(l1!=null){
            stack1.push(l1);
            l1=l1.next;
        }
        while(l2!=null){
            stack2.push(l2);
            l2=l2.next;
        }
        //直接在原链表上进行修改并返回最终结果：规定stack1为长链表
        if(stack1.size()<stack2.size()){
            Stack<ListNode> temp=stack1;
            stack1=stack2;
            stack2=temp;
        }
        int add=0;
        while(stack1.size()>0){
            int a=stack1.size()>0?stack1.peek().val:0;
            int b=stack2.size()>0?stack2.peek().val:0;
            int sum=a+b+add;
            add=sum>9?1:0;
            ListNode tail=stack1.pop();
            tail.val=sum%10;
            if(stack2.size()>0) stack2.pop();
            //最终首位计算完后还存在进位，那么需要开辟新的头结点
            if(stack1.size()==0){
                if(add==0) return tail;
                else return new ListNode(1,tail);
            } 
        }
        return null;
    }
}