摘要：
在LeetCode中，链表复制复杂指针问题是一个经典的算法题目。该问题要求在不破坏原始链表结构的情况下，复制一个包含额外指针的链表。本文将围绕这一主题，通过哈希表两次遍历的策略，详细解析并实现这一算法。
一、问题背景
链表复制复杂指针问题来源于LeetCode的第138题，问题描述如下：
给定一个链表的头节点head，其中每个节点包含一个额外的随机指针random，该指针可以指向链表中的任意节点或者null。要求复制这个链表，使得新链表中的每个节点都对应原链表中的一个节点，同时保持随机指针的复制。
二、解决方案
为了解决这个问题，我们可以采用哈希表来辅助我们完成复制。以下是具体的解决方案：
1. 创建一个哈希表，用于存储原链表节点和新链表节点的映射关系。
2. 遍历原链表，创建新链表节点，并将原链表节点和新链表节点存入哈希表中。
3. 遍历原链表，根据随机指针在哈希表中找到对应的新链表节点，并设置新链表的随机指针。
4. 分离原链表和新链表。
三、代码实现
下面是使用Python语言实现的代码：
python
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
创建哈希表
hash_map = {}
创建新链表节点，并存储映射关系
cur = head
while cur:
new_node = Node(cur.val)
hash_map[cur] = new_node
cur = cur.next
设置新链表的next和random指针
cur = head
while cur:
new_node = hash_map[cur]
new_node.next = hash_map.get(cur.next)
new_node.random = hash_map.get(cur.random)
cur = cur.next
分离原链表和新链表
cur = head
new_head = hash_map.get(head)
while cur:
new_node = hash_map[cur]
new_node.next = new_node.next.next if new_node.next else None
cur.next = cur.next.next if cur.next else None
cur = cur.next
return new_head
测试代码
def print_list(node):
while node:
random_val = node.random.val if node.random else None
print(f"Value: {node.val}, Random: {random_val}")
node = node.next
创建测试链表
node1 = Node(1)
node2 = Node(2)
node3 = Node(3)
node1.next = node2
node2.next = node3
node2.random = node1
node3.random = node2
复制链表
new_head = copyRandomList(node1)
打印原链表和新链表
print("Original List:")
print_list(node1)
print("Copied List:")
print_list(new_head)
四、总结
本文通过哈希表两次遍历的策略，详细解析并实现了LeetCode链表复制复杂指针问题。在实际应用中，我们可以根据具体场景选择合适的算法，以达到最优的性能。
Comments NOTHING