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

递归大法好！dummy.next = addInList1(node,new ListNode(1)); 这句是解题关键！

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) {
        ListNode h1 = reverse(head1);
        ListNode h2 = reverse(head2);
        ListNode fin = addInList1(h1,h2);
        ListNode finnal = reverse(fin);
        return finnal;
    }
    public ListNode addInList1(ListNode h1,ListNode h2){
        ListNode res = new ListNode(-1);
        ListNode dummy = res;
        boolean flag = false;
        while(h1!=null && h2!=null){
            int tmp = 0;
            if(flag){
                tmp = h1.val+h2.val+1;
            }else{
                tmp = h1.val+h2.val;
            }
            if(tmp/10>=1){
                tmp = tmp-10;
                flag = true;
            }else{
                flag = false;
            }
            ListNode phead = new ListNode(tmp);
            dummy.next = phead;
            dummy = dummy.next;
            h1 = h1.next;
            h2 = h2.next;
        }
        ListNode node = h1==null?h2:h1;
        if(flag){
            dummy.next = addInList1(node,new ListNode(1));           
        }else{
            dummy.next = node;
        }
        return res.next;
    }
    public ListNode reverse(ListNode head){
        ListNode cur = head;
        ListNode pre = null;
        while(cur!=null){
            ListNode tmp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }
}