leetcode的两数相加

image.png

1. 总结

开始使用迭代实现后，后续使用的递归实现。

1.1 遇到的坑

1. 想要删除链表中的节点，必须持有该节点的上一个节点。若只知道待删除节点的引用，是无法在链表中删除的。

image.png

1.2 获得的经验

1. 链表的整数运算中，除10表示进的位数，取余10表示剩余的位数。
2. 递归就是分治，需要递归出口，以及最终使用分-治，还是治-分；
   2.1 分-治：即先执行递归方法，而后执行业务操作；
   2.2 治-分：先执行业务操作，再执行递归方法；
   分析题目可知，需要从链表头进行计算，故先进行“治”再“分”。
3. 因为链表单向性，要善于使用引用保存链表的起始位置；

1.3 得到教训

链表操作时，为了不失去去尾节点的控制，最好每次迭代/递归返回上一个节点的引用。

2. 代码实现

public class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

2.1 迭代实现

class Solution {
    /**
     * 引用的问题
     * 1. 链表中，持有的是尾结点对象的引用，将引用置为空。
     * 但是尾结点对象依旧存在，若是让尾节点在链表中设置为空，要获取到尾节点的上一个节点引用，将其从链中删除
     * <p>
     * <p>
     * 解答成功:
     * 执行耗时:2 ms,击败了99.98% 的Java用户
     * 内存消耗:38.6 MB,击败了80.31% 的Java用户
     */
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {

        ListNode result = new ListNode();
        result.next = new ListNode();
        ListNode r1 = result.next;

        //均不为空的情况
        int x1 = 0;
        while (l1 != null || l2 != null) {
            int v1 = l1 != null ? l1.val : 0;
            int v2 = l2 != null ? l2.val : 0;
            int x = v1 + v2 + x1;
            int x2;
            if (x != 0) {
                //需要进的位数
                x1 = x / 10;
                //自己需要存储的位数
                x2 = x % 10;
            } else {
                x1 = 0;
                x2 = 0;
            }
            result = result.next;
            result.val = x2;
            result.next = new ListNode();
            //持有对象
            l1 = l1 != null ? l1.next : null;
            l2 = l2 != null ? l2.next : null;
        }
        if (x1 != 0) {
            result.next.val = x1;
        } else {
            result.next = null;
        }
        return r1;
    }
}

2.2 递归实现

每次递归前，节点指向下一节点，但是递归方法中传递的是本节点。当尾节点的val为0时，因为拿到的尾节点上一个节点的引用，是可以删除尾结点的。

class Solution {

    /**
     * 解答成功:
     * 执行耗时:2 ms,击败了99.98% 的Java用户
     * 内存消耗:38.6 MB,击败了78.95% 的Java用户
     * <p>
     * 递归-分治
     * <p>
     * 该逻辑需要先治再分。先执行逻辑，然后再递归
     * 1. 递归出口
     * 2. 中间逻辑
     * <p>
     * [0,0]
     */
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {

        ListNode listNode = new ListNode();
        listNode.next = new ListNode();
        ListNode r = listNode.next;
        addTwoNumber(l1, l2, 0, listNode);
        return r;
    }

    /**
     * 1. 若想删除链表中的节点，必须知道上一个节点的引用，
     * 若只知道本节点引用是无法删除链表中节点；
     * <p>
     * 2. 递归  -  分治    治分
     * <p>
     * 3. 链表的整数运算中，除表示进的位数，取余表示剩余的位数。
     */
    private ListNode addTwoNumber(ListNode l1, ListNode l2, int x2, ListNode result) {
        //递归出口
        if (l1 == null && l2 == null) {
            if (x2 != 0) {
                result.next.val = x2;
            } else {
                result.next = null;
            }
            return result;
        }
        int v1 = l1 != null ? l1.val : 0;
        int v2 = l2 != null ? l2.val : 0;

        int t = v1 + v2 + x2;
        x2 = t / 10;
        int x1 = t % 10;

        //赋值
        result = result.next;

        result.val = x1;
        result.next = new ListNode();
        return addTwoNumber(l1 != null ? l1.next : null, l2 != null ? l2.next : null, x2, result);
    }
}