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

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) {
        ListNode head;
        ArrayList<Integer> list1=new ArrayList<>();
        ArrayList<Integer> list2=new ArrayList<>();
        ArrayList<Integer> list3=new ArrayList<>();
        //获得head1链表的集合
        while (head1!=null){
            list1.add(head1.val);
            head1=head1.next;
        }
        //获得head2链表的集合
        while (head2!=null){
            list2.add(head2.val);
            head2=head2.next;
        }
        //长度小的为list1，长度长的为list2
        if(list1.size()>list2.size()){
            list3=list2;
            list2=list1;
            list1=list3;
        }

        //list3赋初值，长度为list2的长度+1--为了保留进一的位数
        list3=new ArrayList<>();
        for(int j=0;j<list2.size()+1;j++){
            list3.add(0);
        }
        //反转list1，list2集合，从低位数开始加
        Collections.reverse(list1);
        Collections.reverse(list2);
        //补齐位数，让list1和list2同位数
        for(int x=list1.size();x<list2.size();x++){
            list1.add(0);
        }
        //加法运算，结果存到list3
        for(int i=0;i<list2.size();i++){
            int t=list3.get(i)+list1.get(i)+list2.get(i);
            if(t>9){
                list3.set(i,t-10);
                list3.set(i+1,1);//进1
            }else{
                list3.set(i,t);
            }
        }
        //如果list最后一位为0，则去掉
        if(list3.get(list3.size()-1)==0){
            list3.remove(list3.size()-1);
        }
        //反转list3，并构建链表
        Collections.reverse(list3);
        head=new ListNode(list3.get(0));
        ListNode cur=head;
        for(int j=1;j<list3.size();j++){
            cur.next=new ListNode(list3.get(j));
            cur=cur.next;
        }
        return head;
    }
}