25 复杂链表的复制

题目描述

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个指向任意节点），请实现函数复制这个复杂链表。

解题思路

方法一：哈希表

核心思想：使用哈希表存储原节点到新节点的映射，分两次遍历完成复制。

方法二：原地复制

核心思想：

1. 在原链表每个节点后插入一个复制节点
2. 设置复制节点的random指针
3. 将链表拆分成原链表和新链表

时间复杂度：O(n) 空间复杂度：O(n)（方法一）或 O(1)（方法二）

Python 实现

class RandomListNode:
    def __init__(self, label=0, next=None, random=None):
        self.label = label
        self.next = next
        self.random = random


# 方法一：哈希表
def clone_with_hashmap(head):
    """
    使用哈希表复制复杂链表
    """
    if not head:
        return None

    # 创建新节点，建立映射
    node_map = {}
    curr = head
    while curr:
        node_map[curr] = RandomListNode(curr.label)
        curr = curr.next

    # 设置next和random指针
    curr = head
    while curr:
        if curr.next:
            node_map[curr].next = node_map[curr.next]
        if curr.random:
            node_map[curr].random = node_map[curr.random]
        curr = curr.next

    return node_map[head]


# 方法二：原地复制
def clone_in_place(head):
    """
    原地复制复杂链表
    """
    if not head:
        return None

    # 1. 在每个节点后插入复制节点
    curr = head
    while curr:
        clone = RandomListNode(curr.label)
        clone.next = curr.next
        curr.next = clone
        curr = clone.next

    # 2. 设置random指针
    curr = head
    while curr:
        if curr.random:
            curr.next.random = curr.random.next
        curr = curr.next.next

    # 3. 拆分链表
    curr = head
    clone_head = head.next
    while curr:
        clone = curr.next
        curr.next = clone.next
        if clone.next:
            clone.next = clone.next.next
        curr = curr.next

    return clone_head


# 测试代码
if __name__ == "__main__":
    # 创建复杂链表: 1 -> 2 -> 3 -> None
    # random: 1.random -> 3, 2.random -> 1, 3.random -> None
    node1 = RandomListNode(1)
    node2 = RandomListNode(2)
    node3 = RandomListNode(3)
    node1.next = node2
    node2.next = node3
    node1.random = node3
    node2.random = node1

    # 复制
    cloned = clone_with_hashmap(node1)

    # 验证
    print(f"原链表: {node1.label} -> {node1.next.label} -> {node1.next.next.label}")
    print(f"复制链表: {cloned.label} -> {cloned.next.label} -> {cloned.next.next.label}")
    print(f"node1.random: {node1.random.label}, cloned.random: {cloned.random.label}")

图解

原地复制法步骤:

步骤1: 在每个节点后插入复制节点
原:  1 -> 2 -> 3 -> None
插入: 1 -> 1' -> 2 -> 2' -> 3 -> 3' -> None

步骤2: 设置random指针
1.random = 3  →  1'.random = 3'
2.random = 1  →  2'.random = 1'
3.random = None → 3'.random = None

步骤3: 拆分链表
原链表:  1 -> 2 -> 3 -> None
新链表:  1' -> 2' -> 3' -> None