链表复制带随机指针优化（一次遍历）
在数据结构与算法的学习过程中，链表是一种非常重要的数据结构。链表由一系列节点组成，每个节点包含数据和指向下一个节点的指针。在LeetCode等编程竞赛平台中，链表相关的题目也是高频出现。其中，链表复制带随机指针的问题是一个经典的难题，要求在不破坏原链表结构的情况下，复制出一个新的链表，且新链表的每个节点除了具有与原链表节点相同的数据外，还包含一个指向原链表中某个节点的随机指针。
传统的解法需要两次遍历原链表，但我们可以通过一次遍历来实现这一目标。本文将围绕这一主题，详细讲解如何使用一次遍历的方法解决链表复制带随机指针的问题。
题目描述
给定一个链表的头节点 `head`，链表中的每个节点包含以下信息：
- `val`：一个整数值。
- `next`：指向链表中下一个节点的指针。
- `random`：指向链表中任意一个节点的指针（可以为 `null`）。
要求复制这个链表，并返回新链表的头节点。新链表中的节点应该与原链表中的节点一一对应，且新链表中的节点除了具有与原链表节点相同的数据外，还包含一个指向原链表中某个节点的随机指针。
解题思路
为了实现一次遍历复制链表，我们可以采用以下步骤：
1. 创建映射表：遍历原链表，创建一个映射表，将原链表中的节点映射到新链表中的对应节点。
2. 复制节点：遍历原链表，根据映射表复制节点，并设置新节点的 `next` 和 `random` 指针。
3. 分离链表：将复制的链表分离出来，返回新链表的头节点。
代码实现
以下是使用一次遍历实现链表复制的代码示例：
python
class Node:
def __init__(self, val=0, next=None, random=None):
self.val = val
self.next = next
self.random = random
class Solution:
def copyRandomList(self, head: 'Node') -> 'Node':
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:
old_to_new[cur].next = old_to_new[cur.next]
old_to_new[cur].random = old_to_new[cur.random]
cur = cur.next
分离链表
new_head = old_to_new[head]
cur = head
while cur:
old_to_new[cur].next = cur.next
cur.next = old_to_new[cur].next
cur = cur.next
return new_head
分析与优化
1. 空间复杂度：上述代码中，我们使用了额外的映射表来存储原链表节点和新链表节点的对应关系，因此空间复杂度为 O(N)。
2. 时间复杂度：代码中包含三次遍历原链表的操作，因此时间复杂度为 O(N)。
总结
本文详细讲解了如何使用一次遍历的方法解决链表复制带随机指针的问题。通过创建映射表、复制节点和分离链表三个步骤，我们可以在不破坏原链表结构的情况下，高效地复制出一个新的链表。在实际应用中，我们可以根据具体需求对代码进行优化，以达到更好的性能。
Comments NOTHING