具有随机指针的链表的深层副本

基础概念

具有随机指针的链表是一种特殊的链表结构，其中每个节点除了包含数据和一个指向下一个节点的指针外，还包含一个指向链表中任意节点或者null的随机指针。这种结构增加了链表的复杂性，因为它需要在复制时正确地处理这些随机指针。

类型

简单链表：每个节点只有一个指向下一个节点的指针。
具有随机指针的链表：每个节点有一个数据域、一个指向下一个节点的指针和一个指向链表中任意节点或null的随机指针。

应用场景

缓存系统：使用随机指针来快速访问最近使用的数据。
图结构表示：链表节点可以代表图的顶点，随机指针可以代表边。
复杂数据结构的实现：如跳表、散列表等。

实现深层副本的步骤

创建新节点：遍历原始链表，为每个节点创建一个新节点，并将新节点插入到原节点和下一个原节点之间。
设置随机指针：再次遍历链表，这次设置新节点的随机指针，使其指向对应的新节点。
拆分链表：最后遍历链表，将新旧节点分离，形成两个独立的链表。

示例代码

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
    
    # Step 1: Create new nodes and insert them into the original list
    current = head
    while current:
        new_node = Node(current.val, current.next)
        current.next = new_node
        current = new_node.next
    
    # Step 2: Set 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: Split the list into two lists
    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