克隆链表，其中每个节点都有一个指向链表中任何其他节点的随机指针

克隆一个包含随机指针的链表是一个复杂的问题，因为它涉及到不仅要复制节点的值和下一个指针，还要复制随机指针指向的节点。下面是解决这个问题的基础概念、步骤和相关代码示例。

基础概念

链表：一种数据结构，其中每个元素都是一个独立的对象，称为节点，通过指针连接。
随机指针：链表中的一个指针，它可以指向链表中的任何节点或者null。

解决方案

克隆包含随机指针的链表通常有两种方法：使用哈希表和使用拼接。

方法一：使用哈希表

遍历原始链表，创建新节点，并将原始节点和新节点的映射存储在哈希表中。
再次遍历原始链表，使用哈希表来设置新节点的next和random指针。

优势：逻辑简单，易于理解。 应用场景：适用于链表不是特别长的情况。

代码示例：

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
    
    # 创建一个哈希表来存储原始节点和新节点的映射
    node_map = {}
    
    # 第一次遍历：创建所有节点的副本并存储在哈希表中
    current = head
    while current:
        node_map[current] = Node(current.val)
        current = current.next
    
    # 第二次遍历：设置新节点的next和random指针
    current = head
    while current:
        if current.next:
            node_map[current].next = node_map[current.next]
        if current.random:
            node_map[current].random = node_map[current.random]
        current = current.next
    
    return node_map[head]

方法二：使用拼接

遍历原始链表，在每个节点后面插入一个新节点，其值与原节点相同。
再次遍历链表，设置新节点的random指针。
最后，拆分原始链表和新链表。

优势：不需要额外的存储空间来存储映射关系。 应用场景：适用于内存受限的环境。

代码示例：

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
    
    # 第一次遍历：在每个节点后面插入新节点
    current = head
    while current:
        new_node = Node(current.val, current.next)
        current.next = new_node
        current = new_node.next
    
    # 第二次遍历：设置新节点的random指针
    current = head
    while current:
        if current.random:
            current.next.random = current.random.next
        current = current.next.next
    
    # 第三次遍历：拆分原始链表和新链表
    new_head = head.next
    current = head
    while current:
        new_node = current.next
        current.next = new_node.next
        if new_node.next:
            new_node.next = new_node.next.next
        current = current.next
    
    return new_head