2. 两数相加

2. 两数相加

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

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

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

示例

示例1

输入：l1 = [2,4,3], l2 = [5,6,4]

输出：[7,0,8]

解释：342 + 465 = 807.

示例2

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

输出：[0]

示例3

输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]

输出：[8,9,9,9,0,0,0,1]

代码

javascript

export function ListNodeJs(val, next) {
  this.val = (val === undefined ? 0 : val)
  this.next = (next === undefined ? null : next)
}

typescript

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)
  }
}

javascript

// 2. 两数相加
// https://leetcode.cn/problems/add-two-numbers/

import { ListNodeJs } from "../../utilsJs"

export function addTwoNumbers(l1, l2) {
  let result = null
  let middleVal = null
  let advanced = 0
  while(l1 || l2) {
    const l1Val = l1 ? l1.val : 0
    const l2Val = l2 ? l2.val : 0
    const sum = l1Val + l2Val + advanced
    if (!result) {
      result = middleVal = new ListNodeJs((sum) % 10)
    } else {
      middleVal.next = new ListNodeJs((sum) % 10)
      middleVal = middleVal.next
    }
    advanced = Math.floor((sum) / 10)
    if (l1) {
      l1 = l1.next
    }
    if (l2) {
      l2 = l2.next
    }
  }
  if (advanced > 0) {
    middleVal.next = new ListNodeJs(advanced)
  }
  return result
};

typescript

// 2. 两数相加
// https://leetcode.cn/problems/add-two-numbers/

import { ListNode } from "../../utils"

export function addTwoNumbers(l1: ListNode | null, l2: ListNode | null): ListNode | null {
  let result: ListNode | null = null
  let middleVal: ListNode | null = null
  let advanced: number = 0
  while(l1 || l2) {
    const l1Val = l1 ? l1.val : 0
    const l2Val = l2 ? l2.val : 0
    const sum = l1Val + l2Val + advanced
    if (!result) {
      result = middleVal = new ListNode((sum) % 10)
    } else {
      (middleVal as ListNode).next = new ListNode((sum) % 10)
      middleVal = (middleVal as ListNode).next
    }
    advanced = Math.floor((sum) / 10)
    if (l1) {
      l1 = l1.next
    }
    if (l2) {
      l2 = l2.next
    }
  }
  if (advanced > 0) {
    (middleVal as ListNode).next = new ListNode(advanced)
  }
  return result
};

测试代码

test

import { expect, test } from 'vitest'
import { getListNode } from "../../../src/utils"
import { addTwoNumbers } from './typescript.ts'
import { getListNodeJs } from "../../../src/utilsJs"
import { addTwoNumbers as addTwoNumbersJs } from './javascript.js'

const l1Array = [2, 4, 5]
const l2Array = [5, 6, 4]
const l3Array = [7, 0, 0, 1]

const l4Array = [2, 4, 5]
const l5Array = [5, 6, 4]
const l6Array = [7, 0, 0, 1]

const l1 = getListNode(l1Array)
const l2 = getListNode(l2Array)
const l3 = getListNode(l3Array)

const l4 = getListNode(l4Array)
const l5 = getListNode(l5Array)
const l6 = getListNode(l6Array)

const l7 = getListNodeJs(l1Array)
const l8 = getListNodeJs(l2Array)
const l9 = getListNodeJs(l3Array)

const l10 = getListNodeJs(l4Array)
const l11 = getListNodeJs(l5Array)
const l12 = getListNodeJs(l6Array)

test(`addTwoNumbers(l1, l2) toEqual l3`, () => {
  expect(addTwoNumbers(l1, l2)).toEqual(l3)
})

test(`addTwoNumbers(l4, l5) toEqual l6`, () => {
  expect(addTwoNumbers(l4, l5)).toEqual(l6)
})

test(`addTwoNumbersJs(l7, l8) toEqual l9`, () => {
  expect(addTwoNumbersJs(l7, l8)).toEqual(l9)
})

test(`addTwoNumbersJs(l10, l11) toEqual l12`, () => {
  expect(addTwoNumbersJs(l10, l11)).toEqual(l12)
})