链表复制带随机指针：哈希表与原地复制策略解析
在数据结构与算法的学习过程中，链表是一种非常重要的数据结构。链表由一系列节点组成，每个节点包含数据和指向下一个节点的指针。在某些应用场景中，链表节点可能还包含一个指向随机节点的指针，这种链表被称为带随机指针的链表。在LeetCode等编程竞赛平台中，链表复制带随机指针问题是一个经典的面试题。本文将围绕这一主题，探讨两种解决策略：哈希表和原地复制。
问题分析
给定一个带随机指针的链表，要求复制这个链表，并保持复制后的链表中的每个节点都指向原链表中相应节点的复制节点。具体来说，如果原链表中的节点`node`有一个随机指针指向节点`node.random`，那么复制后的链表中的节点`copyNode`也应该有一个随机指针指向复制后的节点`copyNode.random`。
哈希表策略
基本思路
1. 遍历原链表，创建一个哈希表，将原链表中的节点映射到其对应的复制节点。
2. 遍历原链表，更新每个节点的随机指针指向其复制节点的随机指针。
3. 遍历原链表，分离出原链表和复制链表。
代码实现
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
创建哈希表
old_to_new = {}
遍历原链表，创建哈希表
cur = head
while cur:
old_to_new[cur] = Node(cur.val)
cur = cur.next
更新随机指针
cur = head
while cur:
if cur.random:
old_to_new[cur].random = old_to_new[cur.random]
cur = cur.next
分离原链表和复制链表
cur = head
new_head = old_to_new[cur]
while cur:
old_to_new[cur].next = old_to_new[cur.next]
cur = cur.next
return new_head
优点
- 时间复杂度：O(n)，只需要遍历原链表三次。
- 空间复杂度：O(n)，需要额外的哈希表存储节点映射。
缺点
- 需要额外的空间存储哈希表。
原地复制策略
基本思路
1. 在原链表中插入一个复制节点，复制节点的随机指针指向原节点的随机指针。
2. 遍历原链表，更新复制节点的随机指针。
3. 分离原链表和复制链表。
代码实现
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
在原链表中插入复制节点
cur = head
while cur:
new_node = Node(cur.val)
new_node.next = cur.next
cur.next = new_node
cur = new_node.next
更新随机指针
cur = head
while cur:
if cur.random:
cur.next.random = cur.random.next
cur = cur.next.next
分离原链表和复制链表
cur = head
new_head = head.next
while cur:
new_node = cur.next
cur.next = new_node.next
new_node.next = new_node.next.next if new_node.next else None
cur = cur.next
return new_head
优点
- 时间复杂度：O(n)，只需要遍历原链表三次。
- 空间复杂度：O(1)，不需要额外的空间。
缺点
- 需要修改原链表结构，可能影响后续操作。
总结
本文介绍了两种解决带随机指针的链表复制问题的策略：哈希表和原地复制。哈希表策略简单易懂，但需要额外的空间；原地复制策略空间复杂度低，但需要修改原链表结构。在实际应用中，可以根据具体需求选择合适的策略。
Comments NOTHING