力扣算法题2：两数相加题目解答额外知识

104 阅读 0 评论 69 点赞

我是靠谱客的博主微笑飞机，最近开发中收集的这篇文章主要介绍力扣算法题2：两数相加题目解答额外知识，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目

在这里插入图片描述

解答

我的解答

思路

思考良久，根据正常的两数相加的习惯，逆序存储的数字其实反而更加适合用来做计算，因为你可以从链表的第一个就开始遍历，无需再从后拿个十百千位进行同位相加，所以简单来说就是循环两个数的链表，对同一个位置的数进行相加，如果超过10，则需要进位。

思路是这样没错，可一到实现层面，就懵叉叉了？为什么呢，链表的结构在代码解答的提示中给出了，如下：

/**
 * Definition for singly-linked list.
 * 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; }
 * }
 */

那在代码中如何将每一次的节点都挂在最后一个节点的next上呢？思考良久，我想不出来，所以我看了答案

代码
无
分析
无
结果
无

官方解答

思路

由于输入的两个链表都是逆序存储数字的位数的，因此两个链表中同一位置的数字可以直接相加。
同时遍历两个链表，逐位计算它们的和，并与当前位置的进位值相加。具体而言，如果当前两个链表处相应位置的数字为 n1,n2,进位值为carry，则它们的和为n1+n2+carry；其中，答案链表处相应位置的数字为 (n1+n2+carry) mod 10，而新的进位值为(n1+n2+carry)/10。如果两个链表的长度不同，则可以认为长度短的链表的后面有若干个 0 。此外，如果链表遍历结束后，有arry>0，还需要在答案链表的后面附加一个节点，节点的值为carry。

代码

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    	//定义了一个为空的头和尾节点
        ListNode head = null, tail = null;
        //定义进位参数carry
        int carry = 0;
        // 循环条件为只要任意的两个链表都不为空
        while (l1 != null || l2 != null) {
        	// 如果l1为空则0，不为空则为val值
            int n1 = l1 != null ? l1.val : 0;
            // 如果l2为空则0，不为空则为val值
            int n2 = l2 != null ? l2.val : 0;
            // 计算当前同位的相加值+进位值
            int sum = n1 + n2 + carry;
            // 如果头结点为空，则初始化头尾节点都为当前相加值mod10，即获取相加后的尾数
            if (head == null) {
                head = tail = new ListNode(sum % 10);
            } else {
            	// 不为空，则将尾节点的next设置为当前的计算值
                tail.next = new ListNode(sum % 10);
                // 更新当前的尾节点的地址为上次尾节点的赋值next
                tail = tail.next;
            }
            // 这个时候开始判断是否有进位，即sum会不会超过10
            carry = sum / 10;
            // 循环下一个节点
            if (l1 != null) {
                l1 = l1.next;
            }
            if (l2 != null) {
                l2 = l2.next;
            }
        }
       // 获取进位数值
        if (carry > 0) {
            tail.next = new ListNode(carry);
        }
    	// 返回整个链表结果
        return head;
    }
}

分析

时间复杂度：O(max(m,n)，其中 m 和 n 分别为两个链表的长度。我们要遍历两个链表的全部位置，而处理每个位置只需要 O(1) 的时间。

空间复杂度：O(1)。注意返回值不计入空间复杂度。
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

从思路上来看是跟我想的差不多，实现代码中，关键是通过tail = tail.next将当前循环相加的结果保存在结果链表的尾端，这是我没想到的，回想一下，其实数据结构中有提高过的，只是我不熟悉，大意了。

结果

大佬解答

思路

我仔细分析了下大佬的代码和思路，代码比官方的简洁而且少了一些必要的空间开销。其实关键在于有些条件的判断和少了一些赋值，详细看代码注释解析

代码

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
   		 // 定义一个root节点作为头结点，并初始化val为0
        ListNode root = new ListNode(0);
        // 定义尾节点初始化为root，此时cursor的内存地址就是指向root
        ListNode cursor = root;
        // 定义进位的标志，初始化为0
        int carry = 0;
        // 循环有三个条件，前两个必须，后面这个为什么加上呢，如果进位不为0，也需要同样需要一次生成到尾节点的操作
        // 减少了单独判断的代码
        while(l1 != null || l2 != null || carry != 0) {
            // 如果l1为空则0，不为空则为val值
            int l1Val = l1 != null ? l1.val : 0;
            // 如果l2为空则0，不为空则为val值
            int l2Val = l2 != null ? l2.val : 0;
            // 计算当前同位的相加值+进位值
            int sumVal = l1Val + l2Val + carry;
            // 获取进位数值
            carry = sumVal / 10;
            // 新生成一个统计节点，val为相加总和 mod 10
            ListNode sumNode = new ListNode(sumVal % 10);
            // 先将统计节点放在cursor之后，一次循环cursor为root，则相当于在root后加入一个尾节点
            cursor.next = sumNode;
            // 再将统计节点设置赋值给cursor，此时cursor的指针指向了sumNode，但是sumNode此时又是root的尾节点
            // 相当于cursor又变成root的尾节点了，代码等同于cursor = cursor.next
            cursor = sumNode;
            // 循环下一个节点
            if(l1 != null) {
                l1 = l1.next;
            }
            if(l2 != null) {
                l2 = l2.next;
            }
        }
        // 由于root从0开始，所以需要返回第一个节点的next之后的链表
        return root.next;
    }
}