复制带随机指针的链表

题目分析

本题考察的是如何实现复杂链表的深拷贝。每个节点除了普通的next指针外，还有一个随机指针random，随机指针可能指向链表中的任意节点或null。

解题思路与算法

要实现链表的深拷贝，需要确保复制链表中的random指针也能正确指向新链表中对应的节点，而不是原链表中的节点。

一种高效的解决方法为“三步走”算法：

算法流程：

以下用更直观通俗的方式为你详细解释一下这个问题的三步解题步骤：

步骤一：复制节点并插入到原节点后面（复制值与next）

首先我们有一个链表，比如：

原链表：A → B → C → null

• 我们先对每个节点进行复制，比如A复制为A'，B复制为B'，C复制为C'；
• 然后，把复制出的新节点插入到对应的原节点后面，如：

A → A' → B → B' → C → C' → null

这样做的好处是方便后续操作random指针（原节点和新节点形成了明显的对应关系）。

步骤二：复制随机指针（random）

现在链表变成了：

原节点 → 新节点 → 原节点 → 新节点……

• 因为原节点和新节点是紧挨着的，因此原节点的random指针所指向的节点的下一个节点，就是新节点random指针应指向的节点。
• 比如，如果原节点A的random指向节点C：
  • 那么节点A'的random就应该指向节点C'（节点C的下一个节点）。

例如：

假设A.random → C
则 A'.random = A.random.next = C'

重复这个过程，就可以让新链表的随机指针准确地复制原链表中的指向关系。

步骤三：拆分链表

经过上述两步，我们已经成功地把所有节点及random指针都复制好了。但现在新旧节点还混杂在一起：

A → A' → B → B' → C → C'

最后一步的目的是将其拆分成两个独立的链表：

• 原链表恢复原样：

A → B → C

• 新链表为：

A' → B' → C'

拆分方式就是遍历一次，分别将新旧节点的next指针指向各自链表中的下一个节点。

复杂度分析

• 时间复杂度：$O(n)$，遍历链表三次，每次为$O(n)$。
• 空间复杂度：$O(1)$，未使用额外空间（除了结果链表）。

参考代码

Python代码

class Node:
    def __init__(self, val, next=None, random=None):
        self.val = val
        self.next = next
        self.random = random

def copyRandomList(head):
    if not head:
        return None

    # 第一步：复制节点并插入原节点后面
    cur = head
    while cur:
        copy = Node(cur.val)
        copy.next = cur.next
        cur.next = copy
        cur = copy.next

    # 第二步：复制random指针
    cur = head
    while cur:
        if cur.random:
            cur.next.random = cur.random.next
        cur = cur.next.next

    # 第三步：拆分链表
    cur_old = head
    cur_new = head.next
    new_head = head.next
    while cur_old:
        cur_old.next = cur_old.next.next
        cur_new.next = cur_new.next.next if cur_new.next else None
        cur_old = cur_old.next
        cur_new = cur_new.next

    return new_head

# 处理输入
n = int(input())
nodes_input = [input().split() for _ in range(n)]

# 构建原链表
nodes = [Node(int(val)) for val, _ in nodes_input]
for i in range(n):
    if i < n - 1:
        nodes[i].next = nodes[i + 1]
    random_idx = int(nodes_input[i][1])
    nodes[i].random = nodes[random_idx] if random_idx != -1 else None

# 复制链表
new_head = copyRandomList(nodes[0] if nodes else None)

# 输出结果
cur = new_head
new_nodes = []
while cur:
    new_nodes.append(cur)
    cur = cur.next

for node in new_nodes:
    random_index = -1
    if node.random:
        tmp = new_head
        random_index = 0
        # 从头遍历链表找到random节点的索引
        while tmp != node.random:
            tmp = tmp.next
            random_index += 1
    print(f"{node.val} {random_index}")

Java代码

import java.util.Scanner;

class Node {
    int val;
    Node next, random;
    Node(int val) { this.val = val; }
}

public class Main {
    public static Node copyRandomList(Node head) {
        if (head == null) return null;
        Node cur = head;
        
        // 第一步：复制节点并插入原节点后面
        while (cur != null) {
            Node copy = new Node(cur.val);
            copy.next = cur.next;
            cur.next = copy;
            cur = copy.next;
        }
        
        // 第二步：复制random指针
        cur = head;
        while (cur != null) {
            if (cur.random != null)
                cur.next.random = cur.random.next;
            cur = cur.next.next;
        }

        // 第三步：拆分链表
        Node oldCur = head, newHead = head.next, newCur = newHead;
        while (oldCur != null) {
            oldCur.next = oldCur.next.next;
            newCur.next = (newCur.next != null) ? newCur.next.next : null;
            oldCur = oldCur.next;
            newCur = newCur.next;
        }

        return newHead;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        Node[] originalNodes = new Node[n];
        int[] randomIdx = new int[n];
        
        for (int i = 0; i < n; i++) {
            originalNodes[i] = new Node(sc.nextInt());
            randomIdx[i] = sc.nextInt();
        }
        
        for (int i = 0; i < n; i++) {
            if (i < n - 1) originalNodes[i].next = originalNodes[i + 1];
            originalNodes[i].random = randomIdx[i] == -1 ? null : originalNodes[randomIdx[i]];
        }
        
        Node res = copyRandomList(n > 0 ? originalNodes[0] : null);

        // 输出
        Node cur = res;
        Node tmp;
        while (cur != null) {
            // 为确定random的索引，需要从链表头遍历计算索引
            int random_index = -1;
            if (cur.random != null) {
                random_index = 0;
                tmp = res;
                while (tmp != cur.random) {
                    tmp = tmp.next;
                    random_index++;
                }
            }
            System.out.println(cur.val + " " + random_index);
            cur = cur.next;
        }
    }
}

C++代码

#include <iostream>
#include <vector>

using namespace std;

struct Node {
    int val;
    Node *next, *random;
    Node(int x) : val(x), next(nullptr), random(nullptr) {}
};

Node* copyRandomList(Node* head) {
    if (!head) return nullptr;
    Node* cur = head;

    // 第一步：复制节点
    while (cur) {
        Node* copy = new Node(cur->val);
        copy->next = cur->next;
        cur->next = copy;
        cur = copy->next;
    }

    // 第二步：复制random指针
    cur = head;
    while (cur) {
        if (cur->random)
            cur->next->random = cur->random->next;
        cur = cur->next->next;
    }

    // 第三步：拆分链表
    Node* oldCur = head, *newHead = head->next, *newCur = newHead;
    while (oldCur) {
        oldCur->next = oldCur->next->next;
        newCur->next = newCur->next ? newCur->next->next : nullptr;
        oldCur = oldCur->next;
        newCur = newCur->next;
    }

    return newHead;
}

int main() {
    int n;
    cin >> n;
    vector<Node*> nodes(n);
    vector<int> randomIdx(n);

    for (int i = 0; i < n; i++) {
        int val, r;
        cin >> val >> r;
        nodes[i] = new Node(val);
        randomIdx[i] = r;
    }

    for (int i = 0; i < n; i++) {
        if (i < n - 1) nodes[i]->next = nodes[i + 1];
        nodes[i]->random = randomIdx[i] == -1 ? nullptr : nodes[randomIdx[i]];
    }

    Node* res = copyRandomList(n > 0 ? nodes[0] : nullptr);

    // 输出新链表节点值与random索引
    Node* cur = res;
    while (cur) {
        int random_index = -1;
        if (cur->random) {
            random_index = 0;
            Node* tmp = res;
            while (tmp && tmp != cur->random) {
                tmp = tmp->next;
                random_index++;
            }
        }
        cout << cur->val << " " << random_index << endl;
        cur = cur->next;
    }

    return 0;
}

```。

题目内容

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

构造这个链表的 深拷贝。 深拷贝应该正好由 $n$个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 $next$ 指针和 $random$ 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点。

例如，如果原链表中有 $X$ 和 $Y$ 两个节点，其中 $X.random --> Y$ 。那么在复制链表中对应的两个节点 $x$ 和 $y$ ，同样有 $x.random --> y$ 。

返回复制链表的头节点。

用一个由 $n$ 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 $[val, random_index]$ 表示：

• $val$：一个表示 $Node.val$ 的整数。
• random_index：随机指针指向的节点索引（范围从 $0$ 到 $n-1$）；如果不指向任何节点，则为 $null$ 。

你的代码只接受原链表的头节点 $head$ 作为传入参数。

输入描述

输入包含多行。

第一行包含一个整数 $n$，表示链表的长度。

接下来 $n$ 行，每行包含两个值，表示链表每个节点的情况：

• 第一个值为节点的整数值 val。
• 第二个值为随机指针指向节点的索引（从 $0$ 开始计数），若随机指针为 null，则用 -1 表示。

节点按输入顺序连接。

输出描述

输出共 $n$ 行，每行两个值，与输入格式相同，表示新链表中每个节点的 val 和 random 指针的索引。

样例1

输入

5
7 -1
13 0
11 4
10 2
1 0

输出

7 -1
13 0
11 4
10 2
1 0

样例2

输入

2
1 1
2 1

输出

1 1
2 1

样例3

输入

3
3 -1
3 0
3 -1

输出

3 -1
3 0
3 -1

提示

• $0 <= n <= 1000$
• $-10^4 <= Node.val <= 10^4$
• $Node.random$ 为 $null$或指向链表中的节点。