002:两数相加
本题采用了 哈希表 与 链表 的知识。原题链接
题干
给你两个 非空 的链表,表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的,并且每个节点只能存储 一位 数字。
请你将两个数相加,并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外,这两个数都不会以 0 开头。
题解
首先写出边界条件。
if (l1 === null || l2 === null) {
return null;
}
本题主要需要考虑进位位,因此需要单独一个变量来表示是否存在进位。随后,根据题目描述,我们可以在一个链表结束后为其接上一个 value
为 0,next
为 null
的新节点。由于不会有 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;
}

This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
▲
▼