题目描述

在链表的算法题中，有一种特殊类型的问题叫做“随机链表的复制”。假设你有一个链表，链表的每个节点不仅包含整数值，还包含一个指向链表中任意一个节点（包括它自己）的随机指针（称为 random 指针）。我们要求复制这个链表，使得复制后的链表不仅保持了原有的值结构和顺序，而且每个节点的 random 指针也要正确地指向复制链表中的对应节点。

为了解决这个问题，我们需要一种方法来确保在复制过程中，原链表和复制链表中的节点能够正确地关联起来。一个常用的策略是先在每个原始节点后面插入一个对应的复制节点，然后再处理 random 指针，最后拆开链表恢复原始结构。

示例代码

PHP 示例

class Node {
    public $val;
    public $next;
    public $random;

    function __construct($val = 0, $next = null, $random = null) {
        $this->val = $val;
        $this->next = $next;
        $this->random = $random;
    }
}

function copyRandomList($head) {
    if ($head == null) return null;

    // Step 1: Copy nodes and put them next to the original nodes
    $current = $head;
    while ($current != null) {
        $newNode = new Node($current->val, $current->next, null);
        $current->next = $newNode;
        $current = $newNode->next;
    }

    // Step 2: Set the random pointers for the copied nodes
    $current = $head;
    while ($current != null) {
        if ($current->random != null) {
            $current->next->random = $current->random->next;
        }
        $current = $current->next->next;
    }

    // Step 3: Split the nodes
    $copiedHead = $head->next;
    $original = $head;
    $copied = $copiedHead;
    while ($copied != null && $original->next != null) {
        $original->next = $original->next->next;
        $copied->next = ($copied->next != null) ? $copied->next->next : null;
        $original = $original->next;
        $copied = $copied->next;
    }

    return $copiedHead;
}

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
    current = head
    while current:
        new_node = Node(current.val, current.next, None)
        current.next = new_node
        current = new_node.next

    # Step 2
    current = head
    while current:
        if current.random:
            current.next.random = current.random.next
        current = current.next.next

    # Step 3
    copied_head = head.next
    original = head
    copied = copied_head
    while copied and original.next:
        original.next = original.next.next
        copied.next = (copied.next if copied.next else None)
        original = original.next
        copied = copied.next

    return copied_head

JavaScript 示例

class Node {
    constructor(val = 0, next = null, random = null) {
        this.val = val;
        this.next = next;
        this.random = random;
    }
}

function copyRandomList(head) {
    if (!head) return null;

    // Step 1
    let current = head;
    while (current) {
        const newNode = new Node(current.val, current.next, null);
        current.next = newNode;
        current = newNode.next;
    }

    // Step 2
    current = head;
    while (current) {
        if (current.random) {
            current.next.random = current.random.next;
        }
        current = current.next.next;
    }

    // Step 3
    let copiedHead = head.next;
    let original = head;
    let copied = copiedHead;
    while (copied && original.next) {
        original.next = original.next.next;
        copied.next = copied.next ? copied.next.next : null;
        original = original.next;
        copied = copied.next;
    }

    return copiedHead;
}

在以上代码中，我们首先遍历链表，在每个节点后面插入一个复制的节点。然后，我们再次遍历链表，设置复制节点的 random 指针。最后，我们将链表拆分回两个独立的链表：原始链表和复制链表，并返回复制链表的头节点。这种方法的空间复杂度为 O(1)（除了用于复制的节点外，没有使用额外的空间），时间复杂度为 O(n)，其中 n 是链表的长度。