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

进步感受：

这次又是可以自己解决问题了，虽然用了stack，浪费了空间，但是，时间上是差不多的，下次可以改进。

解题思路：

最🐔仔的是，拿链表翻转，就可以实现从低开始相加了！！！！

import java.util.*;

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

public class Solution {

    public ListNode addInList (ListNode head1, ListNode head2) {
        if(head1 == null || head2 == null) {
            return null;
        } 

        ListNode p1 = reverseListNode(head1);
        ListNode p2 = reverseListNode(head2);
        ListNode res = new ListNode(0);
        ListNode cur = res;

        int carry = 0;
        while(p1!=null || p2!= null || carry>0) {
            // 获取当前节点相加的值
            int value1 = p1!=null?p1.val:0;
            int value2 = p2!=null?p2.val:0;
            int temp = value1 + value2 + carry;
            carry = temp / 10;

            // 生成节点添加到链表
            cur.next = new ListNode(temp%10);
            cur = cur.next;
            
            // 遍历下个节点
            p1 = p1==null? null: p1.next;
            p2 = p2==null? null: p2.next;
        }

        // 这里要小心因为我们是从小位开始添加的节点
        // 所以是000001这样的，要翻转
        return reverseListNode(res.next);
    }

    public ListNode reverseListNode(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        while(cur!=null) {
            ListNode temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }

    /**
     * 我的实现方法，空间复杂度太高
     * 遍历次数太多了。
     * @param head1 ListNode类
     * @param head2 ListNode类
     * @return ListNode类
     */
    public ListNode addInList2 (ListNode head1, ListNode head2) {
        // write code here
        Stack<Integer> s1 = new Stack<Integer>();
        Stack<Integer> s2 = new Stack<Integer>();
        Stack<Integer> s3 = new Stack<Integer>();

        while (head1 != null) {
            s1.push(head1.val);
            head1 = head1.next;
        }

        while (head2 != null) {
            s2.push(head2.val);
            head2 = head2.next;
        }

        ListNode res = new ListNode(0);
        ListNode cur = res;
        int result = 0;
        int enter = 0;
        while(!s1.isEmpty() || !s2.isEmpty()) {
            int value1 = s1.isEmpty()? 0: s1.pop();
            int value2 = s2.isEmpty()? 0: s2.pop();
            int value = value1 + value2 + enter;
            enter = value >= 10 ? 1 : 0;
            int point = value % 10;
            s3.push(point);
        }

        if(enter == 1) {
            s3.push(enter);
        }

        while(!s3.isEmpty()) {
            cur.next = new ListNode(s3.pop());
            cur = cur.next;
        }

        return res.next;
    }


}