Pcrab's blog 


002:两数相加


本题采用了 哈希表链表 的知识。原题链接

题干

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

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

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

题解

首先写出边界条件。

if (l1 === null || l2 === null) {
    return null;
}

本题主要需要考虑进位位,因此需要单独一个变量来表示是否存在进位。随后,根据题目描述,我们可以在一个链表结束后为其接上一个 value 为 0,nextnull
的新节点。由于不会有 0 出现在最后一位,因此当两个链表都是 0 且下一位都是 null 时就结束了,最后如果有进位则补 1,没有则输出最后的结果。

export class ListNode {
    val: number;
    next: ListNode | null;
    constructor(val?: number, next?: ListNode | null) {
        this.val = val === undefined ? 0 : val;
        this.next = next === undefined ? null : next;
    }
}

function addTwoNumbers(l1: ListNode | null, l2: ListNode | null): ListNode | null {
    // 一个都没有
    if (l1 === null || l2 === null) {
        return null;
    }

    // 初始化节点
    const resultNode = new ListNode();
    let tmpNode = resultNode;
    let add = 0;
    let l1Node: ListNode | null = l1;
    let l2Node: ListNode | null = l2;

    while (l1Node !== null || l2Node !== null || add !== 0) {
        const tmpNodeVal = (l1Node?.val || 0) + (l2Node?.val || 0) + add;
        add = tmpNodeVal >= 10 ? 1 : 0;
        tmpNode.next = new ListNode(tmpNodeVal % 10);
        tmpNode = tmpNode.next;
        l1Node = l1Node?.next || null;
        l2Node = l2Node?.next || null;
    }
    return resultNode.next;
}






:D 获取中...


© - Pcrab - 2022 - Powered by Hexo Theme Quark