Algorithm

Appearance

138. 复制带随机指针的链表 ​

  • 题号：138
  • 来源：LeetCode
  • 难度：中等
  • 标签：链表 哈希表
  • 语言：TypeScript
  • 解法：1 个
  • 作者：lmliheng
  • 最近更新：2026-09-27

TypeScript · O(n) 时间 · O(n) 空间 · 更新于 2026-09-27

哈希表映射原节点到副本，再连指针

typescript
/**
 * @difficulty medium
 * @tags 链表,哈希表
 * @time O(n)
 * @space O(n)
 * @note 哈希表映射原节点到副本，再连指针
 * @138. 复制带随机指针的链表
 */

class _Node {
    val: number
    next: _Node | null
    random: _Node | null

    constructor(val?: number, next?: _Node, random?: _Node) {
        this.val = (val === undefined ? 0 : val)
        this.next = (next === undefined ? null : next)
        this.random = (random === undefined ? null : random)
    }

}

let head = new _Node(1, new _Node(2))

if (head === null) {
    console.log(head)
}
let map = new Map()
for (let cur: _Node | null = head; cur !== null; cur = cur.next) {
    map.set(cur, new _Node(cur.val))
}

for (let cur: _Node | null = head; cur !== null; cur = cur.next) {
    let copyNode = map.get(cur)
    copyNode.next = cur.next ? map.get(cur.next) : null
    copyNode.random = cur.random ? map.get(cur.random) : null

}
console.log(map.get(head)) // map中存储的是地址

源码：ts/leetcode/138. 复制带随机指针的链表.ts

在 GitHub 上查看题目所在目录：lmliheng/algorithm