LeetCode如何实现复杂链表的复制

在LeetCode上，复杂链表的复制是一个经典的问题，通常出现在面试题中。这个问题的难点在于链表中不仅包含普通的next指针，还包含一个random指针，该指针可以指向链表中的任意节点或null。我们需要在不破坏原链表结构的情况下，复制出一个新的链表，并且新链表中的random指针也要正确指向新链表中的节点。

本文将详细介绍如何实现复杂链表的复制，并通过代码示例来帮助理解。

问题描述

给定一个复杂链表的头节点head，链表中每个节点除了有一个next指针指向下一个节点外，还有一个random指针指向链表中的任意节点或null。请实现一个函数来复制这个链表，并返回复制后的链表的头节点。

示例

输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

在这个示例中，链表的每个节点包含两个指针：next和random。我们需要复制这个链表，并确保新链表中的random指针指向正确的位置。

解题思路

方法一：哈希表法

我们可以使用哈希表来存储原链表节点和新链表节点之间的映射关系。具体步骤如下：

1. 遍历原链表：首先遍历原链表，创建新链表的节点，并将原节点和新节点的映射关系存储在哈希表中。
2. 设置next和random指针：再次遍历原链表，根据哈希表中的映射关系，设置新链表中每个节点的next和random指针。
3. 返回新链表的头节点：最后返回新链表的头节点。

代码实现

class Node:
    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
        self.val = int(x)
        self.next = next
        self.random = random

def copyRandomList(head: 'Node') -> 'Node':
    if not head:
        return None
    
    # 创建哈希表，存储原节点和新节点的映射关系
    mapping = {}
    
    # 第一次遍历，创建新节点并存储映射关系
    current = head
    while current:
        mapping[current] = Node(current.val)
        current = current.next
    
    # 第二次遍历，设置新节点的next和random指针
    current = head
    while current:
        if current.next:
            mapping[current].next = mapping[current.next]
        if current.random:
            mapping[current].random = mapping[current.random]
        current = current.next
    
    # 返回新链表的头节点
    return mapping[head]

复杂度分析

• 时间复杂度：O(N)，其中N是链表的长度。我们需要遍历链表两次。
• 空间复杂度：O(N)，哈希表存储了原链表和新链表的映射关系。

方法二：原地复制法

我们可以通过原地复制的方式来减少空间复杂度。具体步骤如下：

1. 复制节点：遍历原链表，在每个节点后面插入一个复制的新节点。
2. 设置random指针：再次遍历链表，设置新节点的random指针。
3. 分离链表：最后将原链表和新链表分离。

代码实现

def copyRandomList(head: 'Node') -> 'Node':
    if not head:
        return None
    
    # 第一步：复制节点并插入到原节点后面
    current = head
    while current:
        new_node = Node(current.val)
        new_node.next = current.next
        current.next = new_node
        current = new_node.next
    
    # 第二步：设置新节点的random指针
    current = head
    while current:
        if current.random:
            current.next.random = current.random.next
        current = current.next.next
    
    # 第三步：分离原链表和新链表
    current = head
    new_head = head.next
    while current:
        new_node = current.next
        current.next = new_node.next
        if new_node.next:
            new_node.next = new_node.next.next
        current = current.next
    
    return new_head

复杂度分析

• 时间复杂度：O(N)，其中N是链表的长度。我们需要遍历链表三次。
• 空间复杂度：O(1)，我们只使用了常数级别的额外空间。

总结

复杂链表的复制问题可以通过哈希表法或原地复制法来解决。哈希表法的思路简单直观，但需要额外的空间来存储映射关系；而原地复制法则通过巧妙地修改链表结构，避免了额外的空间开销。在实际应用中，可以根据具体需求选择合适的方法。

通过本文的介绍，相信读者已经对如何实现复杂链表的复制有了深入的理解。希望这篇文章能够帮助你在LeetCode上顺利解决类似的问题。