【学习打卡】第七天 数据结构和算法

链表 - 两数相加（leetcode - 2）

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.

输入：l1 = [0], l2 = [0]
输出：[0]

输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]

思路

1. 创建两个指针分别指向输入的链表l1和l2
2. 创建输出链表l3，同时创建第三个指针指向l3
3. 遍历l1和l2，当前节点相加
4. 得到的商单独声明一个变量，用来下个节点相加
5. 得到的余数放到l3当前节点
6. 最后返回链表l3

// 自己写的
var addTwoNumbers = function(l1, l2) {
    let l3 = new ListNode(0)
    let p1 = l1;
    let p2 = l2;
    let p3 = l3;
    let carry = 0;
    while(p1 || p2) {
        let val1 = p1? p1.val : 0;
        let val2 = p2 ? p2.val : 0;
        let total = val1 + val2 + carry;

        carry = Math.floor(total / 10);
        p3.val = total % 10;
        if((p1 && p1.next) || (p2 && p2.next)) {
            p3.next = new ListNode(0);
            p3 = p3.next;
        }
        
        if(p1) p1 = p1.next;
        if(p2) p2 = p2.next;
        
    }
    if(carry) {
        p3.next = new ListNode(carry)
    }
    return l3;
};

// 视频中老师的解法
var addTwoNumbers = function(l1, l2) {
    let l3 = new ListNode(0)
    let p1 = l1;
    let p2 = l2;
    let p3 = l3;
    let carry = 0;
    while(p1 || p2) {
        let val1 = p1? p1.val : 0;
        let val2 = p2 ? p2.val : 0;
        let total = val1 + val2 + carry;

        carry = Math.floor(total / 10);
        p3.next = new ListNode(total % 10);
        
        if(p1) p1 = p1.next;
        if(p2) p2 = p2.next;
        p3 = p3.next;
        
    }
    if(carry) {
        p3.next = new ListNode(carry)
    }
    return l3.next;
};

// leetcode的官方写法
var addTwoNumbers = function(l1, l2) {
    let head = null, tail = null;
    let carry = 0;
    while (l1 || l2) {
        const n1 = l1 ? l1.val : 0;
        const n2 = l2 ? l2.val : 0;
        const sum = n1 + n2 + carry;
        if (!head) {
            head = tail = new ListNode(sum % 10);
        } else {
            tail.next = new ListNode(sum % 10);
            tail = tail.next;
        }
        carry = Math.floor(sum / 10);
        if (l1) {
            l1 = l1.next;
        }
        if (l2) {
            l2 = l2.next;
        }
    }
    if (carry > 0) {
        tail.next = new ListNode(carry);
    }
    return head;
};

反思：

1. 自己的写法和leetcode的写法比较相似，都是初始化链表第一个节点，但是自己的在相加之前就初始化了，leetcode是在相加之后再一起初始化，相比来说，leetcode更加优雅一些。
2. 老师的写法是初始化链表的前一个节点，最后返回初始化节点的next
3. 三种写法的时间复杂度和空间复杂度相同；时间复杂度O(n)，空间复杂度O(n)，n是链表节点的最大节点数