企业官网建设流程全解析

下面是 LeetCode 138「随机链表的复制」的 Kotlin 实现。提供两种常见解法：哈希表法（简单直观）和原地复制法（O(1) 额外空间）。

节点类定义

classNode(var`val`:Int){varnext:Node?=nullvarrandom:Node?=null}

Kotlin 中 val 是关键字，作为属性名需用反引号包裹，与 LeetCode 默认定义一致。

方法一：哈希表（推荐）

两轮遍历：第一轮复制节点值并建立 原节点 -> 新节点 映射；第二轮设置新节点的 next 和 random。

funcopyRandomList(head:Node?):Node?{if(head==null)returnnull// 1. 复制所有节点，存入哈希表valmap=HashMap<Node,Node>()varcur=headwhile(cur!=null){map[cur]=Node(cur.`val`)cur=cur.next}// 2. 连接 next 和 randomcur=headwhile(cur!=null){valcopy=map[cur]!!copy.next=cur.next?.let{map[it]}copy.random=cur.random?.let{map[it]}cur=cur.next}returnmap[head]}

关键点：

· cur.next?.let { map[it] }：安全调用，若 next 非空则从哈希表取出对应新节点，否则返回 null。
· map[cur]!!：确定当前节点已在第一轮被复制，可断言非空。

方法二：原地复制（O(1) 额外空间）

分三步：

1. 在每个原节点后插入其复制节点；
2. 利用原节点的 random 设置复制节点的 random；
3. 将复制节点从原链表中拆分成新链表。

funcopyRandomList(head:Node?):Node?{if(head==null)returnnull// 1. 复制节点并插入到原节点之后：A -> A' -> B -> B' -> ...varcur=headwhile(cur!=null){valcopy=Node(cur.`val`)copy.next=cur.next cur.next=copy cur=copy.next}// 2. 设置复制节点的 randomcur=headwhile(cur!=null){cur.next!!.random=cur.random?.next cur=cur.next?.next}// 3. 拆分两个链表valdummy=Node(0)varcopyCur:Node?=dummy cur=headwhile(cur!=null){valcopy=cur.next!!copyCur!!.next=copy copyCur=copy cur.next=copy.next cur=cur.next}returndummy.next}

关键点：

· 第 2 步中 cur.random?.next 恰好是原 random 节点的复制节点。
· 第 3 步拆分时，copy.next 指向原链表的下一个原节点，恢复原链表并构建新链表。

复杂度分析

方法 时间复杂度 空间复杂度
哈希表 O(n) O(n)
原地复制 O(n) O(1)

建议：面试中优先写哈希表法，逻辑清晰不易出错；若面试官要求优化空间，再使用原地复制法。