随机链表的复制

题目要求

你需要实现一个算法来复制一个特殊的链表，在这个链表中，每个节点除了有一个next指针指向下一个节点，还有一个random指针，它可以指向链表中的任意节点或者是空节点。你的任务是创建这个链表的一个深拷贝，这意味着你需要创建一份完全新的节点集合，使得：

1. 每个新节点的值与原链表中的对应节点的值相同。
2. 新节点的next指针指向复制链表中的下一个新节点。
3. 新节点的random指针指向复制链表中的新节点，这些新节点对应于原链表中被random指针指向的节点。
4. 不应有任何指针指向原链表中的节点，即复制链表应该是完全独立的。

最终，你需要返回新复制链表的头节点。

解题思路

解决这个问题的关键是如何处理random指针的复制。以下是一个高效的解题步骤：

1. 遍历原链表，创建新节点：

   • 遍历原链表，对于每个原节点创建一个新节点。
   • 将新节点插入到原节点和原节点的下一个节点之间。
   • 例如，原链表是 A -> B -> C，变换后的链表是 A -> A' -> B -> B' -> C -> C'，其中 A', B', C'是新创建的节点的深拷贝。

2. 复制random指针：

   • 再次遍历链表，复制random指针。由于新节点是紧跟在原节点后面的，可以通过original_node.random.next来设置新节点的random指针（如果original_node.random不为空的话）。

3. 拆分链表：

   • 最后，将这个交错的链表拆分为原链表和复制链表。
   • 遍历链表，将原节点的next指向next.next，将复制节点的next指向next.next（如果next不为空的话）。
   • 同时恢复原链表的结构。

这个方法的优点是不需要额外的空间来存储节点间的对应关系，因为复制节点紧跟在原节点后面，可以通过原链表直接定位到复制链表的节点。这样，我们就可以在不使用额外空间的情况下完成random指针的复制。

Golang 版本

type Node struct {
    Val int
    Next *Node
    Random *Node
}

func copyRandomList(head *Node) *Node {
    if head == nil {
        return nil
    }

    // Step 1: Create a new node for each node and insert it right after the original one.
    for current := head; current != nil; current = current.Next.Next {
        newNode := &Node{Val: current.Val}
        newNode.Next = current.Next
        current.Next = newNode
    }

    // Step 2: Copy the random pointers for the new nodes.
    for current := head; current != nil; current = current.Next.Next {
        if current.Random != nil {
            current.Next.Random = current.Random.Next
        }
    }

    // Step 3: Separate the combined list into the original list and the copied list.
    pseudoHead := &Node{}
    copyCurrent := pseudoHead
    for current := head; current != nil; current = current.Next {
        // Extract the copy
        copyCurrent.Next = current.Next
        copyCurrent = copyCurrent.Next

        // Restore the original list
        current.Next = current.Next.Next
    }

    return pseudoHead.Next
}

这段代码实现了上述的解题思路，首先在原链表的每个节点后面插入了一个新的节点，然后复制了random指针，最后将这个交错的链表拆分成了原链表和复制链表。这样，我们就得到了原链表的深拷贝。

C++版本

#include <iostream>
using namespace std;

// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;

    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};

class Solution {
public:
    Node* copyRandomList(Node* head) {
        if (!head) return nullptr;

        // Step 1: Create a new node for each node and insert it right after the original one.
        for (Node* node = head; node != nullptr; node = node->next->next) {
            Node* newNode = new Node(node->val);
            newNode->next = node->next;
            node->next = newNode;
        }

        // Step 2: Copy the random pointers for the new nodes.
        for (Node* node = head; node != nullptr; node = node->next->next) {
            if (node->random) {
                node->next->random = node->random->next;
            }
        }

        // Step 3: Separate the combined list into the original list and the copied list.
        Node* newHead = head->next;
        for (Node* node = head; node != nullptr; node = node->next) {
            Node* newNode = node->next;
            node->next = newNode->next;
            if (newNode->next) newNode->next = newNode->next->next;
        }

        return newHead;
    }
};

int main() {
    // Use the Solution class as you want to test the copyRandomList function.
    return 0;
}

这段 C++代码实现了链表的深拷贝，其中包含了对random指针的特殊处理。它首先在每个原始节点后面插入一个新的节点，然后设置新节点的random指针，最后将这个交错的链表拆分成原始链表和复制链表。

Python 版本

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

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

    # Step 1: Create a new node for each node and insert it right after the original one.
    current = head
    while current:
        new_node = Node(current.val, current.next)
        current.next = new_node
        current = new_node.next

    # Step 2: Copy the random pointers for the new nodes.
    current = head
    while current:
        if current.random:
            current.next.random = current.random.next
        current = current.next.next

    # Step 3: Separate the combined list into the original list and the copied list.
    pseudo_head = Node(0)
    copy_current, current = pseudo_head, head
    while current:
        next_orig = current.next.next
        # Extract the copy
        copy_current.next = current.next
        copy_current = copy_current.next
        # Restore the original list
        current.next = next_orig
        current = next_orig

    return pseudo_head.next

这段 Python 代码实现了链表的深拷贝，包括对random指针的复制。它首先在每个原始节点后面插入一个新的节点，然后设置新节点的random指针，最后将这个交错的链表拆分成原始链表和复制链表。

Java 版本

class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}

public class Solution {
    public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }

        // Step 1: Create a new node for each node and insert it right after the original one.
        Node current = head;
        while (current != null) {
            Node newNode = new Node(current.val);
            newNode.next = current.next;
            current.next = newNode;
            current = newNode.next;
        }

        // Step 2: Copy the random pointers for the new nodes.
        current = head;
        while (current != null) {
            if (current.random != null) {
                current.next.random = current.random.next;
            }
            current = current.next.next;
        }

        // Step 3: Separate the combined list into the original list and the copied list.
        Node pseudoHead = new Node(0);
        Node copy, copyCurrent = pseudoHead;
        current = head;
        while (current != null) {
            next = current.next.next;

            // Extract the copy
            copy = current.next;
            copyCurrent.next = copy;
            copyCurrent = copy;

            // Restore the original list
            current.next = next;

            current = next;
        }

        return pseudoHead.next;
    }
}

这段 Java 代码实现了链表的深拷贝，包括对random指针的复制。它首先在每个原始节点后面插入一个新的节点，然后设置新节点的random指针，最后将这个交错的链表拆分成原始链表和复制链表。

Rust 版本

#![allow(unused)]
fn main() {
// Definition for a Node.
#[derive(Clone, Debug)]
pub struct Node {
    pub val: i32,
    pub next: Option<Box<Node>>,
    pub random: Option<Box<Node>>,
}

impl Node {
    fn new(val: i32) -> Node {
        Node {
            val,
            next: None,
            random: None,
        }
    }
}

pub fn copy_random_list(head: Option<Box<Node>>) -> Option<Box<Node>> {
    let mut head = head;
    let mut current = head.as_mut();

    // Step 1: Create a new node for each node and insert it right after the original one.
    while let Some(node) = current {
        let new_node = Box::new(Node::new(node.val));
        let next = node.next.take();
        node.next = Some(new_node);
        node.next.as_mut().unwrap().next = next;
        current = node.next.as_mut().unwrap().next.as_mut();
    }

    // Step 2: Copy the random pointers for the new nodes.
    current = head.as_mut();
    while let Some(node) = current {
        node.next.as_mut().unwrap().random = node.random.as_ref().map(|random_node| {
            Box::new(Node::new(random_node.val))
        });
        current = node.next.as_mut().unwrap().next.as_mut();
    }

    // Step 3: Separate the combined list into the original list and the copied list.
    let mut pseudo_head = Some(Box::new(Node::new(0)));
    let mut tail = pseudo_head.as_mut();
    current = head.as_mut();
    while let Some(node) = current {
        let next = node.next.as_mut().unwrap().next.take();
        tail.as_mut().unwrap().next = node.next.take();
        tail = tail.unwrap().next.as_mut();
        node.next = next;
        current = node.next.as_mut();
    }

    pseudo_head.unwrap().next
}
}

这段 Rust 代码实现了链表的深拷贝，包括对random指针的复制。它首先在每个原始节点后面插入一个新的节点，然后设置新节点的random指针，最后将这个交错的链表拆分成原始链表和复制链表。由于 Rust 的所有权和借用规则，这段代码在处理指针和节点的所有权时需要特别注意。

总结

上面给出了针对复制带随机指针的链表的解法，涵盖了 Golang、C++、Python、Java 和 Rust 的代码实现。

这个问题的解决思路是通过三个步骤来完成链表的深拷贝：首先在每个原始节点后面插入一个新的节点，然后设置新节点的random指针，最后将这个交错的链表拆分成原始链表和复制链表。这样就能够实现对带随机指针的链表进行深度复制，保持了原链表和复制链表的独立性。