==========================努力奋斗财源广进==========================

一、算法题目

假设链表中每一个节点的值都在 0 - 9 之间，那么链表整体就可以代表一个整数。给定两个这种链表，请生成代表两个整数相加值的结果链表。

二、题解

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) {
        // write code here
        //使用两个栈保存栈。
        ListNode head = new ListNode(-1);
        ListNode dummy = head;
        Stack<ListNode> stack1 = new Stack<>();
        Stack<ListNode> stack2 = new Stack<>();
        Stack<Integer> stack3 = new Stack<>();
        while(head1 != null){
            stack1.push(head1);
            head1 = head1.next;
        }
        while(head2 != null){
            stack2.push(head2);
            head2 = head2.next;
        }
        int count = 0;
        while((!stack1.isEmpty()) && (!stack2.isEmpty())){
            int sum = stack1.pop().val +stack2.pop().val;
            if(count > 0){
                sum += count;
                count--;
            }
            if(sum > 9) {
                sum = sum % 10;
                count++;
            }
            stack3.push(sum);
        }
        while(!stack1.isEmpty()){
            if(count > 0){
                int sum = stack1.pop().val + count;
                if(sum > 9){
                   stack3.push(0);
                   count++;
                } else{
                    stack3.push(sum);
                }
                count--;
            } else{
                stack3.push(stack1.pop().val);
            }
            
        }
        while(!stack2.isEmpty()){
            if(count > 0){
                int sum = stack2.pop().val + count;
                if(sum > 9){
                   stack3.push(0);
                   count++;
                } else{
                    stack3.push(sum);
                }
                count--;
            } else{
                stack3.push(stack2.pop().val);
            }
            
        }
        if(count > 0) stack3.push(1);
        while(!stack3.isEmpty()){
            ListNode tmp = new ListNode(stack3.pop());
            head.next = tmp;
            head = head.next;
        }
        return dummy.next;
    }
}

2、优秀题解

public ListNode addInList (ListNode head1, ListNode head2) {
        // 进行判空处理
        if(head1 == null)
            return head2;
        if(head2 == null){
            return head1;
        }
        // 反转h1链表
        head1 = reverse(head1);
        // 反转h2链表
        head2 = reverse(head2);
        // 创建新的链表头节点
        ListNode head = new ListNode(-1);
        ListNode nHead = head;
        // 记录进位的数值
        int tmp = 0;
        while(head1 != null || head2 != null){
            // val用来累加此时的数值（加数+加数+上一位的进位=当前总的数值）
            int val = tmp;
            // 当节点不为空的时候，则需要加上当前节点的值
            if (head1 != null) {
                val += head1.val;
                head1 = head1.next;
            }
            // 当节点不为空的时候，则需要加上当前节点的值
            if (head2 != null) {
                val += head2.val;
                head2 = head2.next;
            }
            // 求出进位
            tmp = val/10;
            // 进位后剩下的数值即为当前节点的数值
            nHead.next = new ListNode(val%10);
            // 下一个节点
            nHead = nHead.next;

        }
        // 最后当两条链表都加完的时候，进位不为0的时候，则需要再加上这个进位
        if(tmp > 0){
            nHead.next = new ListNode(tmp);
        }
        // 重新反转回来返回
        return reverse(head.next);
    }

    // 反转链表
    ListNode reverse(ListNode head){
        if(head == null)
            return head;
        ListNode cur = head;
        ListNode node = null;
        while(cur != null){
            ListNode tail = cur.next;
            cur.next = node;
            node = cur;
            cur = tail;
        }
        return node;
    }

三、解法心得

自己解法显然是过于复杂，没有使用技巧的简单化解法，完全不顾及占用空间和消耗的时间，优点是能够顺利通过用例。

优秀解法是使用了反转链表，空间复杂度就为O（1）时间复杂度为M+N。思路相对来说还是比较清晰的。后面可以整体复习下。

四、自我监督

评论区记录复习记录