复杂链表深拷贝：随机指针与回溯策略

面试题35探讨的是如何在复杂链表中实现深拷贝，给定的链表每个节点除了常规的next指针外，还有一个额外的random指针，它可以指向链表中的任意节点或者为空。这个链表由整数对[val, random_index]表示，其中val是节点值，random_index是随机指针所指的节点索引。例如，链表`head = [[7,null],[13,0],[11,4],[10,2],[1,0]]`中的第一个节点7没有random指针，第二个节点13的random指针指向第一个节点。 实现深拷贝的方法主要有两种思路： 1. 回溯法（递归） - 使用哈希映射（字典）来存储已经访问过的节点，避免重复复制。当遍历到一个节点时，首先检查它是否已经在哈希表中，若已存在，则返回其复制节点。否则，创建一个新的节点，将其值、next指针和random指针分别设置为原始节点的值、下一个节点和随机节点的复制。然后将新节点加入哈希表，继续递归处理其他节点。 2. O(N)空间的迭代法 - 这种方法不依赖于图的概念，而是迭代遍历链表。在迭代过程中，对于每个节点，先复制当前节点并存储在哈希表中，然后分别复制next指针和random指针，确保所有引用都是独立的副本。迭代完成后，返回复制后的链表头节点。 这两种方法的关键在于处理random指针，无论是通过递归还是迭代，都需要保证复制的链表结构与原链表相同，同时避免形成环路。在实际操作中，要特别注意检查random指针是否已经被复制，以确保正确性。通过这些技术，可以有效地解决复杂链表的深拷贝问题。