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

Posted on Edited on In Views: Word count in article: 732 Reading time ≈ 1 mins.

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

题目链接：138. 复制带随机指针的链表

题目描述

给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。

构造这个链表的 深拷贝。

核心思考：节点拆分与交错拼接

如果使用哈希表存储 原节点 -> 新节点 的映射，可以非常直观地解决问题，但需要 $O(N)$ 的额外空间。本代码采用了一种**无额外空间（除结果集外）**的巧妙算法：节点交错链接法。

  1. 第一步：复制并交错插入
    在原链表的每个节点 A 后面直接插入一个复制节点 A'。链表结构变为 A -> A' -> B -> B' -> ...。这一步使得我们可以直接通过 A.next 找到副本，解决定位问题。
  2. 第二步：设置随机指针
    遍历交错链表。对于每一个副本节点 A'，它的 random 指针应当指向原节点 A.random 的副本，即 A.next.random = A.random.next（注意空指针判断）。
  3. 第三步：拆分链表并还原
    将这个长链表拆分为原链表和新链表。这需要改变 next 指针，将 A -> A' -> B -> B' 恢复为 A -> B 和 A' -> B'。

这种方法的核心价值在于，它利用了链表本身的物理结构作为索引，从而规避了哈希表的开销。

解题思路 (Python)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
"""
# Definition for a Node.
class Node:
    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
        self.val = int(x)
        self.next = next
        self.random = random
"""

class Solution:
    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        if not head:
            return None

        # 1. 构造交错链表: A -> A' -> B -> B'
        cur = head
        while cur:
            copy = Node(cur.val)
            copy.next = cur.next
            cur.next = copy
            cur = copy.next
        
        # 2. 处理 random 指针
        cur = head
        while cur:
            if cur.random:
                cur.next.random = cur.random.next
            cur = cur.next.next

        # 3. 将交错链表拆分，并还原原链表
        cur_ori = head
        dummy = Node(0)
        cur_new = dummy
        
        while cur_ori:
            node = cur_ori.next
            # 提取新链表节点
            cur_new.next = node
            cur_new = cur_new.next
            
            # 还原原链表结构
            cur_ori.next = node.next
            cur_ori = cur_ori.next
        
        return dummy.next

复杂度分析

  • 时间复杂度：$O(N)$，其中 $N$ 是链表的长度。我们共对链表进行了三次线性扫描。
  • 空间复杂度：$O(1)$，如果不考虑存储深拷贝结果所需的节点空间，我们仅使用了常数个指针变量。

ACM 模式

本节提供 ACM 竞赛风格的完整可运行代码，包含输入输出处理。

输入格式：

1
num1 num2 num3 ... numN

输入一行整数数组，以空格分隔。

完整代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
import sys

class Solution:
    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
    if not head:
                return None

            # 1. 构造交错链表: A -> A' -> B -> B'
            cur = head
            while cur:
                copy = Node(cur.val)
                copy.next = cur.next
                cur.next = copy
                cur = copy.next

            # 2. 处理 random 指针
            cur = head
            while cur:
                if cur.random:
                    cur.next.random = cur.random.next
                cur = cur.next.next

            # 3. 将交错链表拆分，并还原原链表
            cur_ori = head
            dummy = Node(0)
            cur_new = dummy

            while cur_ori:
                node = cur_ori.next
                # 提取新链表节点
                cur_new.next = node
                cur_new = cur_new.next

                # 还原原链表结构
                cur_ori.next = node.next
                cur_ori = cur_ori.next

            return dummy.next

def main():
    nums = list(map(int, sys.stdin.read().strip().split()))

    sol = Solution()
    result = sol.copyRandomList(nums)
    print(result)

if __name__ == "__main__":
    main()

运行示例：

1
echo "2 -1 3 4 -5" | python solution.py