链表相加（二）

图解：

链接

思路：

1.将原先的两个表进行反转，获得新的表头，使得低位对齐

2.将两个表对应节点相加

3.将最后的相加的结果的表再进行一次反转

代码

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    public ListNode ReverseList(ListNode head){
        ListNode pre=null;
        ListNode cur=head;
        ListNode cur_next;
        while(cur!=null){
             cur_next=cur.next;
             cur.next=pre;
             pre=cur;
             cur=cur_next;
        }
        return pre;
    }
    //将两个链表相加，传入两个链表的头结点
    public ListNode addInList (ListNode head1, ListNode head2) {
        //先进行判断一下，如果有一个链表为空，那么就不需要进行相加，直接返回非空的链表
        if(head1==null){
            return head2;
        }
        if(head2==null){
            return head1;
        }
        //由于两个链表不能逆着遍历，又因为进行相加要低位对齐，所以先将两个表进行反转
        head1=ReverseList(head1);
        head2=ReverseList(head2);
        //res表示进位，temp表示相加后的存入链表中的值
        int res=0,temp=0;
        //先创建一个新链表的虚的头结点和一个cur节点
        ListNode dummynode=new ListNode(-1);
        ListNode cur=dummynode;
        //只要还有一个表为非空或者还有进位就需要继续循环
        while(head1!=null||head2!=null||res!=0){
            //先判断一下链表的节点，如果是null，就赋值为0，否则就获得链表的节点的值
            int val1=(head1==null)?0:head1.val;
            int val2=(head2==null)?0:head2.val;
            temp=val1+val2+res;
            res=temp/10;
            temp=temp%10;
            //新创建一个节点，存入相加取余10后的结果，存入新的节点中
            //将cur指向新的节点进行连接，并更新cur为下一个节点
            cur.next=new ListNode(temp);
            cur=cur.next;
            //如果当前的头结点为非空，就向后移动一个节点，否则就没有必要移动了，因为都是null,对应的值都为0
            if(head1!=null){
                head1=head1.next;
            }
            if(head2!=null){
                head2=head2.next;
            }
        }
        //最后再将结果的表反转一下就是两个表相加的结果
        return ReverseList(dummynode.next);
    }
}