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

import java.util.*;

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

/**
1.栈方法，LinkedList实现了栈的接口，可以当做栈使用，还能存储ListNode，不存在类型冲突
    1.首先定义两个LinkedList，分别将数据存入其中
    2.定义新的链表及相关辅助结点head,cur,定义进位
    3一个个取出进行操作，循环条件为栈不为空，且进位不为0
    4.移动链表，改变指针位置，实现新链表的输出并返回头结点，既最新结点
    
    代码如下：
    public class Solution {
    /**
     * 
     * @param head1 ListNode类 
     * @param head2 ListNode类 
     * @return ListNode类
    public ListNode addInList (ListNode head1, ListNode head2) {
        // write code here
         //反转链表
      LinkedList<Integer> stack1=new LinkedList<>();
      LinkedList<Integer> stack2=new LinkedList<>();
     //将链表放入栈中
        ListNode a=head1;//定义辅助结点，遍历
        ListNode b=head2;
        while(a!=null){
            stack1.push(a.val);
            a=a.next;
        }
        
         while(b!=null){
            stack2.push(b.val);
            b=b.next;
        }
        
        int carry=0;//进位
        ListNode head=null;
        ListNode cur=null;
        while(!stack1.isEmpty()||!stack2.isEmpty()||carry!=0){
            int x=stack1.isEmpty()?0:stack1.pop();
            int y=stack2.isEmpty()?0:stack2.pop();
            int sum=x+y+carry;
            carry=sum/10;//跟新进位
            head=new ListNode(sum%10);
            head.next=cur;
            cur=head;//跟新结点位置，相当于从后往前加入结点
        }
        return head;  
    }
}
   
方法2：先逆序，再相加
        1.定义一个逆序链表的函数，分别是实现链表的逆序
        2.遍历链表，进行相加，条件依旧是链表不为空且进位不为0
        3.反向添加结点，并返回；
        代码如下：
        import java.util.*;
public class Solution {
    /**
     * 
     * @param head1 ListNode类 
     * @param head2 ListNode类 
     * @return ListNode类
     
    public ListNode addInList (ListNode head1, ListNode head2) {
        // write code here
        //反转两个链表
        head1=reverseList(head1);
        head2=reverseList(head2);
        ListNode head=null;//添加表头
        ListNode cur=null;//辅助遍历结点
        int carry=0;
        while(head1!=null||head2!=null||carry!=0){
            int x=head1==null?0:head1.val;
            int y=head2==null?0:head2.val;
            int sum=x+y+carry;
            carry=sum/10;
            cur=new ListNode(sum%10);
            cur.next=head;//反向添加结点
            head=cur;
            //移动链表
            if(head1!=null){
                head1=head1.next;
            }
             if(head2!=null){
                head2=head2.next;
            }
        }
        
        return cur;  
    }
       //反转链表
     public ListNode reverseList(ListNode pHead){
         //定义一个表头
         ListNode head=null;
         ListNode cur=pHead;
         while(cur!=null){
             ListNode temp=cur.next;//保存下一结结点
             cur.next=head;//反转链表
             //更新结点位置
             head=cur;
             cur=temp;
         }
         return head;
     }   
}
        
        
   
*/
import java.util.*;
public class Solution {
    /**
     * 
     * @param head1 ListNode类 
     * @param head2 ListNode类 
     * @return ListNode类
     */
    public ListNode addInList (ListNode head1, ListNode head2) {
        // write code here
        //反转两个链表
        head1=reverseList(head1);
        head2=reverseList(head2);
        ListNode head=null;//添加表头
        ListNode cur=null;//辅助遍历结点
        int carry=0;
        while(head1!=null||head2!=null||carry!=0){
            int x=head1==null?0:head1.val;
            int y=head2==null?0:head2.val;
            int sum=x+y+carry;
            carry=sum/10;
            cur=new ListNode(sum%10);
            cur.next=head;//反向添加结点
            head=cur;
            //移动链表
            if(head1!=null){
                head1=head1.next;
            }
             if(head2!=null){
                head2=head2.next;
            }
        }
        
        return cur;  
    }
       //反转链表
     public ListNode reverseList(ListNode pHead){
         //定义一个表头
         ListNode head=null;
         ListNode cur=pHead;
         while(cur!=null){
             ListNode temp=cur.next;//保存下一结结点
             cur.next=head;//反转链表
             //更新结点位置
             head=cur;
             cur=temp;
         }
         return head;
     }   
}