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

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) {
        // write code here
        if (head1 == null){
            return head2;

        }
        if(head2 == null){
            return head1;
        }
	  //注释的部分是另一个思路，但是耗内存，没通过
        // Stack<ListNode> list1 = new Stack<ListNode>();
        // Stack<ListNode> list2 = new Stack<ListNode>();
        // Stack<ListNode> resultStack = new Stack<ListNode>();
        // ListNode result = new ListNode(-1);
        // ListNode vNode = result;

        // while(head1 != null){
        //     list1.push(head1);
        //     head1 = head1.next;

        // }

        // while(head2 != null){
        //     list2.push(head2);
        //     head2 = head2.next;

        // }
        // int sn = 0;

        // while(!list1.empty() && !list2.empty()){
        //     int count = 0;
        //     count = list1.pop().val+list2.pop().val+sn;
        //     if(count >= 10){
        //         sn = 1;
        //         ListNode temp = new ListNode(count%10);
        //         resultStack.push(temp);
        //     }else{
        //         sn =  0;
        //         ListNode temp = new ListNode(count);
        //         resultStack.push(temp);

        //     }

        // }

        // while(!list1.empty()){
        //     int count = list1.pop().val+sn;
        //     if(count >= 10){
        //         sn = 1;
        //         ListNode temp = new ListNode(count%10);
        //         resultStack.push(temp);
        //     }else{
        //         sn =  0;
        //         ListNode temp = new ListNode(count);
        //         resultStack.push(temp);

        //     }

        // }

        // while(!list2.empty()){
        //     int count = list2.pop().val+sn;
        //     if(count >= 10){
        //         sn = 1;
        //         ListNode temp = new ListNode(count%10);
        //         resultStack.push(temp);
        //     }else{
        //         sn =  0;
        //         ListNode temp = new ListNode(count);
        //         resultStack.push(temp);

        //     }
        // }

        // if(sn == 1){
        //     ListNode temp = new ListNode (1);
        //     resultStack.push(temp);

        // }



        // while( !resultStack.empty() ){
        //     result = resultStack.pop();
        //     result = result.next;
        // }

        // return vNode.next;

        head1 = ReverseList(head1);
        head2 = ReverseList(head2);

        ListNode head = new ListNode(-1);
        ListNode vNode = head;

        int sn = 0;

        while(head1 != null || head2 != null){
            int val = sn;

            if( head1 != null){
                val += head1.val;
                head1 = head1.next;

            }

            if( head2 != null){
                val += head2.val;
                head2 = head2.next;

            }

            sn = val/10;

            vNode.next = new ListNode(val%10);
            vNode = vNode.next;



        }
        if (sn > 0){
            vNode.next = new ListNode(sn);
        }

        return ReverseList(head.next);


    }

    public ListNode ReverseList (ListNode head) {
        // write code here
        ListNode pre  = null;
        ListNode cur  = head;

        while(cur != null){
            ListNode cur_Next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = cur_Next;

        }
        return pre;
    }



}