下面是 LeetCode 138「随机链表的复制」的 Kotlin 实现。提供两种常见解法哈希表法简单直观和原地复制法O(1) 额外空间。节点类定义classNode(varval:Int){varnext:Node?nullvarrandom:Node?null}Kotlin 中 val 是关键字作为属性名需用反引号包裹与 LeetCode 默认定义一致。方法一哈希表推荐两轮遍历第一轮复制节点值并建立 原节点 - 新节点 映射第二轮设置新节点的 next 和 random。funcopyRandomList(head:Node?):Node?{if(headnull)returnnull// 1. 复制所有节点存入哈希表valmapHashMapNode,Node()varcurheadwhile(cur!null){map[cur]Node(cur.val)curcur.next}// 2. 连接 next 和 randomcurheadwhile(cur!null){valcopymap[cur]!!copy.nextcur.next?.let{map[it]}copy.randomcur.random?.let{map[it]}curcur.next}returnmap[head]}关键点· cur.next?.let { map[it] }安全调用若 next 非空则从哈希表取出对应新节点否则返回 null。· map[cur]!!确定当前节点已在第一轮被复制可断言非空。方法二原地复制O(1) 额外空间分三步在每个原节点后插入其复制节点利用原节点的 random 设置复制节点的 random将复制节点从原链表中拆分成新链表。funcopyRandomList(head:Node?):Node?{if(headnull)returnnull// 1. 复制节点并插入到原节点之后A - A - B - B - ...varcurheadwhile(cur!null){valcopyNode(cur.val)copy.nextcur.next cur.nextcopy curcopy.next}// 2. 设置复制节点的 randomcurheadwhile(cur!null){cur.next!!.randomcur.random?.next curcur.next?.next}// 3. 拆分两个链表valdummyNode(0)varcopyCur:Node?dummy curheadwhile(cur!null){valcopycur.next!!copyCur!!.nextcopy copyCurcopy cur.nextcopy.next curcur.next}returndummy.next}关键点· 第 2 步中 cur.random?.next 恰好是原 random 节点的复制节点。· 第 3 步拆分时copy.next 指向原链表的下一个原节点恢复原链表并构建新链表。复杂度分析方法 时间复杂度 空间复杂度哈希表 O(n) O(n)原地复制 O(n) O(1)建议面试中优先写哈希表法逻辑清晰不易出错若面试官要求优化空间再使用原地复制法。
下面是 LeetCode 138「随机链表的复制」的 Kotlin 实现。提供两种常见解法哈希表法简单直观和原地复制法O(1) 额外空间。节点类定义classNode(varval:Int){varnext:Node?nullvarrandom:Node?null}Kotlin 中 val 是关键字作为属性名需用反引号包裹与 LeetCode 默认定义一致。方法一哈希表推荐两轮遍历第一轮复制节点值并建立 原节点 - 新节点 映射第二轮设置新节点的 next 和 random。funcopyRandomList(head:Node?):Node?{if(headnull)returnnull// 1. 复制所有节点存入哈希表valmapHashMapNode,Node()varcurheadwhile(cur!null){map[cur]Node(cur.val)curcur.next}// 2. 连接 next 和 randomcurheadwhile(cur!null){valcopymap[cur]!!copy.nextcur.next?.let{map[it]}copy.randomcur.random?.let{map[it]}curcur.next}returnmap[head]}关键点· cur.next?.let { map[it] }安全调用若 next 非空则从哈希表取出对应新节点否则返回 null。· map[cur]!!确定当前节点已在第一轮被复制可断言非空。方法二原地复制O(1) 额外空间分三步在每个原节点后插入其复制节点利用原节点的 random 设置复制节点的 random将复制节点从原链表中拆分成新链表。funcopyRandomList(head:Node?):Node?{if(headnull)returnnull// 1. 复制节点并插入到原节点之后A - A - B - B - ...varcurheadwhile(cur!null){valcopyNode(cur.val)copy.nextcur.next cur.nextcopy curcopy.next}// 2. 设置复制节点的 randomcurheadwhile(cur!null){cur.next!!.randomcur.random?.next curcur.next?.next}// 3. 拆分两个链表valdummyNode(0)varcopyCur:Node?dummy curheadwhile(cur!null){valcopycur.next!!copyCur!!.nextcopy copyCurcopy cur.nextcopy.next curcur.next}returndummy.next}关键点· 第 2 步中 cur.random?.next 恰好是原 random 节点的复制节点。· 第 3 步拆分时copy.next 指向原链表的下一个原节点恢复原链表并构建新链表。复杂度分析方法 时间复杂度 空间复杂度哈希表 O(n) O(n)原地复制 O(n) O(1)建议面试中优先写哈希表法逻辑清晰不易出错若面试官要求优化空间再使用原地复制法。
