算法和数据结构之小白（三）

算法

力扣第三题（两数相加）

1. 题目

add.png

2. 思路

• while 循环

3. 解法

• while循环

/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var addTwoNumbers = function(l1, l2) {
    let addOne = 0  // 创建一个头链表用于保存结果
    let sum = new ListNode('0') // 保存头链表的位置用于最后的链表返回
    let head = sum
    while(addOne || l1 || l2) { // 在进位或者两个链表之中有一个存在的前提下执行下面的逻辑
        let val1 = l1 !== null ? l1.val : 0 // 判断值是否存在，不存在补0
        let val2 = l2 !== null ? l2.val : 0 // 判断值是否存在，不存在补0
        let r1 = val1 + val2 + addOne // 求和
        addOne = r1 >= 10 ? 1 : 0 // 如果求和结果>=10，那么进位为1，否则为0
        sum.next = new ListNode(r1 % 10)  // sum的下一个节点
        sum = sum.next /sum指向下一个节点
        if(l1) l1 = l1.next // l1指向下一个节点，以便计算第二个节点的值
        if(l2) l2 = l2.next // l2指向下一个节点，以便计算第二个节点的值
    }
    if(addOne === 1) sum.next = new ListNode(addOne) // 最后一位节点是否有进位
    return head.next // 返回计算结果，之所以用head.next是因为head中保存的第一个节点是刚开始定义的“0”
};

点击提交记录里的通过我们可以看一下我们用了多少时间和空间

while.png

4. 复杂度

• while循环
  时间复杂度O(max(m，n))，循环的次数是链表较长的那个
  空间复杂度O(1)

敞开心扉.png