当前位置： 面试刷题>> 随机链表的复制(经典算法150题)
### 题目描述
在链表的算法题中，有一种特殊类型的问题叫做“随机链表的复制”。假设你有一个链表，链表的每个节点不仅包含整数值，还包含一个指向链表中任意一个节点（包括它自己）的随机指针（称为 `random` 指针）。我们要求复制这个链表，使得复制后的链表不仅保持了原有的值结构和顺序，而且每个节点的 `random` 指针也要正确地指向复制链表中的对应节点。
为了解决这个问题，我们需要一种方法来确保在复制过程中，原链表和复制链表中的节点能够正确地关联起来。一个常用的策略是先在每个原始节点后面插入一个对应的复制节点，然后再处理 `random` 指针，最后拆开链表恢复原始结构。
### 示例代码
#### PHP 示例
```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 示例
```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 示例
```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 是链表的长度。