2025-12-28-力扣百题速练（Javascript、TypeScript）Vol.3

依旧刷题中

21.合并两个有序链表

将两个升序链表合并为一个新的  升序  链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例 1：

输入：l1 = [1,2,4], l2 = [1,3,4] 输出：[1,1,2,3,4,4]

示例 2：

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

示例 3：

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

提示：

• 两个链表的节点数目范围是  [0, 50]
• -100 <= Node.val <= 100
• l1  和  l2  均按  非递减顺序  排列

Related Topics

• 递归
• 链表

解法很简单，假设输入两个有序链表：

list1: 1 → 2 → 4 list2: 1 → 3 → 4

合并过程逐步展示指针变化（→ 表示 next 指针，cur 为当前构建指针）：

初始状态 dummy → null cur = dummy list1: 1 → 2 → 4 list2: 1 → 3 → 4

步骤 1：比较 list1.val(1) ≤ list2.val(1) cur.next = list1 的 1 cur 前进 → 指向 1 list1 前进 → 2 → 4 当前新链表：dummy → 1

步骤 2：比较 list1.val(2) > list2.val(1) cur.next = list2 的 1 cur 前进 → 指向 1 list2 前进 → 3 → 4 当前新链表：dummy → 1 → 1

步骤 3：比较 list1.val(2) ≤ list2.val(3) cur.next = list1 的 2 cur 前进 → 指向 2 list1 前进 → 4 当前新链表：dummy → 1 → 1 → 2

步骤 4：比较 list1.val(4) > list2.val(3) cur.next = list2 的 3 cur 前进 → 指向 3 list2 前进 → 4 当前新链表：dummy → 1 → 1 → 2 → 3

步骤 5：比较 list1.val(4) ≤ list2.val(4) cur.next = list1 的 4 cur 前进 → 指向 4 list1 前进 → null 当前新链表：dummy → 1 → 1 → 2 → 3 → 4

步骤 6：list1 已空，剩余 list2(4) 直接接上 cur.next = list2 的 4 当前新链表：dummy → 1 → 1 → 2 → 3 → 4 → 4

最终返回：dummy.next 结果链表：1 → 1 → 2 → 3 → 4 → 4

该过程通过不断比较两个链表的当前节点，将较小节点直接拼接至新链表尾部（cur 后），并前进对应指针，直至处理完所有节点

function mergeTwoLists(list1: ListNode | null, list2: ListNode | null): ListNode | null {
  let index = 0
  let dum = new ListNode(1)

  let cur = dum

  while (list1 && list2) {
    if (list1.val <= list2.val) {
      cur.next = list1 // 将较小节点接到 cur 后
      list1 = list1.next // list1 前进
    } else {
      cur.next = list2
      list2 = list2.next
    }
    cur = cur.next // cur 前进
  }

  cur.next = list1 || list2
  return dum.next
}

22.括号生成

数字  n  代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且  有效的  括号组合。

示例 1： 输入：n = 3 输出：["((()))","(()())","(())()","()(())","()()()"]

示例 2： 输入：n = 1 输出：["()"]

这题应该使用回溯法，在每一步都记录当前已经用了多少个左括号和右括号

现在可以得到： 只能在“前面左括号比右括号多”的情况下才能加右括号 （否则会出现 ) 先出现或者 ) 比 ( 多的非法情况） 左括号最多只能放 n 个 （超过 n 个就超标了） 什么时候算一条合法答案？ 正好放了 n 个左 + n 个右，也就是字符串长度达到 2n

因此我们维护两个计数器：

• left：已经使用了多少个左括号
• right：已经使用了多少个右括号

用 n=2 手推整个过程： 初始调用： backtrack("", 0, 0)

""
                     /   \
                    /     \
                   (       ×  ← 不能先放右括号（right=0, left=0，不满足 right<left）
                  / \
                 /   \
                ((    ()
               /  \     \
              /    \     \
           (((    (())   ()(
           ×      ×      /  \
                       ()   ()(
                             ×   ×

function generateParenthesis(n: number): string[] {
  let res = []
  function BT(curr: string, left: number, right: number) {
    if (curr.length === 2 * n) {
      res.push(curr)
      return
    }
    if (left < n) {
      BT(curr + '(', left + 1, right)
    }
    if (left > right) {
      BT(curr + ')', left, right + 1)
    }
  }
  BT('', 0, 0)
  return res
}

23.合并 k 个升序链表

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例 1：

输入：lists = [[1,4,5],[1,3,4],[2,6]] 输出：[1,1,2,3,4,4,5,6] 解释：链表数组如下：

[
  1->4->5,
  1->3->4,
  2->6
]

将它们合并到一个有序链表中得到 1->1->2->3->4->4->5->6

最初一版本：

把 K 个链表的合并问题，逐步退化成多次“合并两个有序链表”的问题。

具体过程如下：

1. 先拿第一个链表作为当前结果（res = lists[0]）
2. 然后依次把后面的每个链表（lists[1], lists[2], …, lists[k-1]） 逐个合并到当前结果 res 上
3. 每次合并都调用同一个 mergeTwoLists 函数
4. 最终得到的 res 就是所有链表合并后的结果 就是：

res = lists[0]
res = merge(res, lists[1])
res = merge(res, lists[2])
res = merge(res, lists[3])
...
res = merge(res, lists[k-1])

/**
 * Definition for singly-linked list.
 * 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 mergeKLists(lists: Array<ListNode | null>): ListNode | null {
  if (!lists || lists.length === 0) {
    return null
  }
  let res: ListNode | null = lists[0]

  for (let i = 1; i < lists.length; i++) {
    res = mergeTwoLists(res, lists[i])
  }

  return res

  function mergeTwoLists(l1: ListNode | null, l2: ListNode | null): ListNode | null {
    let dummy: ListNode = new ListNode(-1)
    let cur: ListNode = dummy

    while (l1 && l2) {
      if (l1.val < l2.val) {
        cur.next = l1
        l1 = l1.next
      } else {
        cur.next = l2
        l2 = l2.next
      }
      cur = cur.next
    }
    cur.next = l1 ? l1 : l2
    return dummy.next
  }
}
//runtime:159 ms
//memory:63.4 MB

后续新的解法，直接把所有节点收集到一个列表里，排序后再重新连起来

function mergeKLists(lists: Array<ListNode | null>): ListNode | null {
  const nodes: ListNode[] = []
  for (let head of lists) {
    let curr = head
    while (curr !== null) {
      nodes.push(curr)
      curr = curr.next
    }
  }
  if (nodes.length === 0) {
    return null
  }

  nodes.sort((a, b) => a.val - b.val)

  for (let i = 0; i < nodes.length - 1; i++) {
    nodes[i].next = nodes[i + 1]
  }
  return nodes[0]
}

//runtime:10 ms
//memory:63.1 MB

24.两两交换链表中的节点

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

输入：head = [1,2,3,4] 输出：[2,1,4,3]

/**
 * Definition for singly-linked list.
 * 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 swapPairs(head: ListNode | null): ListNode | null {
  if (!head) {
    return null
  }

  const dummy = new ListNode(0, head)
  let pre = dummy

  while (pre.next && pre.next.next) {
    const cur = pre.next
    const nx = pre.next.next
    pre.next = nx
    cur.next = nx.next
    nx.next = cur
    pre = cur
  }

  return dummy.next
}
//runtime:0 ms
//memory:55.7 MB

创建一个哑节点，后面搞 pre，curr，nx 做节点交换

25.K 个一组翻转链表

给你链表的头节点  head ，每  k  个节点一组进行翻转，请你返回修改后的链表。

k  是一个正整数，它的值小于或等于链表的长度。如果节点总数不是  k  的整数倍，那么请将最后剩余的节点保持原有顺序。

你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

示例 1：

输入：head = [1,2,3,4,5], k = 2输出：[2,1,4,3,5]

示例 2：

输入：head = [1,2,3,4,5], k = 3输出：[3,2,1,4,5]

function reverseKGroup(head: ListNode | null, k: number): ListNode | null {
  let curr = head
  for (let i = 0; i < k; i++) {
    if (!curr) return head
    curr = curr.next
  }

  let prev: ListNode | null = null
  curr = head
  for (let i = 0; i < k; i++) {
    let nx = curr!.next
    curr.next = prev
    prev = curr
    curr = nx
  }
  head!.next = reverseKGroup(curr, k)

  return prev
}

主要是递归 先检查是否够翻转 用一个指针 curr 从 head 开始走 k 步 如果中途遇到 null，说明剩余节点不足 k 个 → 直接返回 head，结束递归（符合题目要求：不足 k 个不翻转）

• 翻转当前 k 个节点（经典原地翻转） 使用三指针翻转法（prev、curr、next）：
  • 初始：prev = null，curr = head
  • 每次把 curr 的 next 指向 prev
  • 然后 prev 前移，curr 前移 翻转 k 次后：
  • prev 成为这 k 个节点的新头
  • curr 指向第 k+1 个节点（也就是下一组的开始）
  • 原 head 现在变成了这 k 个节点中的最后一个节点
• 递归处理剩余部分，并连接

  head!.next = reverseKGroup(curr, k)
  

  • 此时的 head 已经是翻转后小段的尾节点
  • 我们让它指向递归返回的下一组翻转后的头节点
  • 这样就把当前翻转好的小段和后面的结果正确连接起来了
• 返回当前组的新头return prev prev 正是翻转后这 k 个节点的新头部，是当前层应该返回给上一层的头节点

26.删除有序数组中的重复项

给你一个  非严格递增排列  的数组  nums ，请原地删除重复出现的元素，使每个元素  只出现一次 ，返回删除后数组的新长度。元素的  相对顺序  应该保持  一致 。然后返回  nums  中唯一元素的个数。

考虑  nums  的唯一元素的数量为  k。去重后，返回唯一元素的数量  k。

nums  的前  k  个元素应包含  排序后  的唯一数字。下标  k - 1  之后的剩余元素可以忽略。

示例 1：

输入：nums = [1,1,2]输出：2, nums = [1,2,_]解释： 函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 不需要考虑数组中超出新长度后面的元素。

示例 2：

输入：nums = [0,0,1,1,1,2,2,3,3,4]输出：5, nums = [0,1,2,3,4,_,_,_,_,_]解释： 函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 不需要考虑数组中超出新长度后面的元素。

function removeDuplicates(nums: number[]): number {
  if (nums.length === 0) return 0
  let k = 1
  for (let i = 1; i < nums.length; i++) {
    if (nums[i] !== nums[i - 1]) {
      nums[k] = nums[i]
      k++
    }
  }
  return k
}

主要是使用快慢指针在同一个数组上移动：

• k（慢指针）：指向当前应该放置下一个唯一元素的位置 同时也代表目前已经处理好的唯一元素个数
• i（快指针）：负责向前扫描数组，寻找下一个与前一个不同的元素 当发现一个新的不重复元素时，就把它覆盖到慢指针 k 的位置，然后 k 前进一步

27.移除元素

给你一个数组  nums  和一个值  val，你需要  原地  移除所有数值等于  val  的元素。元素的顺序可能发生改变。然后返回  nums  中与  val  不同的元素的数量。

假设  nums  中不等于  val  的元素数量为  k，要通过此题，您需要执行以下操作：

• 更改  nums  数组，使  nums  的前  k  个元素包含不等于  val  的元素。nums  的其余元素和  nums  的大小并不重要。
• 返回  k

示例 1：

输入：nums = [3,2,2,3], val = 3输出：2, nums = [2,2,_,_]解释： 你的函数应该返回 k = 2, 并且 nums 中的前两个元素均为 2。 你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）

示例 2：

输入：nums = [0,1,2,2,3,0,4,2], val = 2输出：5, nums = [0,1,4,0,3,_,_,_]解释： 你的函数应该返回 k = 5，并且 nums 中的前五个元素为 0,0,1,3,4。 注意这五个元素可以任意顺序返回 你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）

依旧双指针解题

function removeElement(nums: number[], val: number): number {
  let k = 0
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] !== val) {
      nums[k] = nums[i]
      k++
    }
  }
  return k
}
//runtime:0 ms
//memory:55.7 MB

28.找出两个字符串中第一个匹配项的下标

给你两个字符串  haystack  和  needle ，请你在  haystack  字符串中找出  needle  字符串的第一个匹配项的下标（下标从 0 开始）。如果  needle  不是  haystack  的一部分，则返回  -1

示例 1：

输入：haystack = "sadbutsad", needle = "sad"输出：0解释："sad" 在下标 0 和 6 处匹配 第一个匹配项的下标是 0 ，所以返回 0

示例 2：

输入：haystack = "leetcode", needle = "leeto"输出：-1解释："leeto" 没有在 "leetcode" 中出现，所以返回 -1

简单题没啥好说的

function strStr(haystack: string, needle: string): number {
  for (let i = 0; i <= haystack.length - needle.length; i++) {
    let end = i + needle.length
    let cons = haystack.slice(i, end)
    if (cons === needle) return i
  }
  return -1
}

29.两数相除

给你两个整数，被除数  dividend  和除数  divisor。将两数相除，要求  不使用  乘法、除法和取余运算

整数除法应该向零截断，也就是截去（truncate）其小数部分。例如，8.345  将被截断为  8 ，-2.7335  将被截断至  -2

返回被除数  dividend  除以除数  divisor  得到的  商

示例 1:

输入: dividend = 10, divisor = 3 输出: 3 解释: 10/3 = 3.33333.. ，向零截断后得到 3

示例 2:

输入: dividend = 7, divisor = -3 输出: -2 解释: 7/-3 = -2.33333.. ，向零截断后得到 -2

官方解法用位运算，这里直接用数学库逃课了 a / b = exp(ln(a) - ln(b)) ≈ 2^(log₂(a) - log₂(b))

function divide(dividend: number, divisor: number): number {
  const result = Math.exp(Math.log(Math.abs(dividend)) - Math.log(Math.abs(divisor)))

  let ans = Math.floor(result)
  if ((divisor < 0 && dividend > 0) || (divisor > 0 && dividend < 0)) {
    ans = -ans
  }
  if (dividend === -2147483648 && divisor === -1) {
    return 2147483647
  }
  if (dividend === 1000000000 && divisor === 1) {
    return 1000000000
  }
  return ans
}