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

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param head1 ListNode类 
     * @param head2 ListNode类 
     * @return ListNode类
     */
    //思路：设置2个栈，分别存放加数链表1、2
    //再设置一个队列，存放sum链表
    //每次各出栈一个，相加求和
    public ListNode addInList (ListNode head1, ListNode head2) {
        // write code here
        Stack<ListNode>add1=new Stack <>();
        Stack<ListNode>add2=new Stack <>();
        Queue<ListNode>sum1=new LinkedList <>();
        //Stack<ListNode>stack
        if(head1==null)return head2;
        if(head2==null)return head1;
        while(head1!=null){
            add1.push(head1);
            head1=head1.next;
        }
        while(head2!=null){
            add2.push(head2);
            head2=head2.next;
        }
        boolean carry=false;
        int add1v=0,add2v=0,sum=0;
        ListNode add1n=null,add2n=null;

        //结束条件：两个队列都为空，如果其中一个为空，则当前+0
        while(!add1.isEmpty()||!add2.isEmpty()){
            if(add1.isEmpty())
                add1v=0;
            else{
                add1n=add1.pop();
                add1v=add1n.val;
                
            }
                
            if(add2.isEmpty())
                add2v=0;
            else{
                add2n=add2.pop();
                add2v=add2n.val;
                
            }  
            if(carry)
                sum=add1v+add2v+1;
            else
                sum=add1v+add2v;
            if(sum>=10){
                sum%=10;
                carry=true;
            }else
                carry=false;
            ListNode sumn=new ListNode(sum);
            System.out.println(sum);
            sum1.offer(sumn);
            
            
        }
        if(carry){
            ListNode sumn=new ListNode(1);
            sum1.offer(sumn);
        }
        ListNode next=sum1.poll();
        ListNode cur=null;
        while(!sum1.isEmpty()){
            cur=sum1.poll();
            cur.next=next;
            next=cur;
        }
        return cur;
    }
}

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) {

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

        boolean carry=false;
        int add1v=0,add2v=0,sum=0;
        head1=reverseList(head1);
        head2=reverseList(head2);
        ListNode add1n=head1,add2n=head2,headSum=new ListNode(-1);
        while(add1n!=null||add2n!=null){
            if(add1n==null)
                add1v=0;
            else{
                add1v=add1n.val;
                add1n=add1n.next;
            }
            if(add2n==null)
                add2v=0;
            else{
                add2v=add2n.val;
                add2n=add2n.next;
            }  
            if(carry)
                sum=add1v+add2v+1;
            else
                sum=add1v+add2v;
            
            if(sum>=10){
                carry=true;
                sum%=10;
            }
            else{
                carry=false;
            }
            //头插法
            ListNode sumn=new ListNode(sum);
            sumn.next=headSum.next;
            headSum.next=sumn;
            
        }
        //最后再判断一次是否有进位
        //头插法
        if(carry){
            ListNode sumn=new ListNode(1);
            sumn.next=headSum.next;
            headSum.next=sumn;
        }
            
        return headSum.next;
    }
    ListNode reverseList(ListNode head){
        if(head==null)return null;
        ListNode cur=head,pre=null,next=null;
        while(cur!=null){
            next=cur.next;
            cur.next=pre;
            pre=cur;
            cur=next;
        }
        return pre;
    }
}