Копирование списка с произвольным указателем: алгоритм O(1) памяти

Зачем это читать?

Представьте: на собеседовании вам дают связанный список, где каждый узел помимо next содержит указатель random, ведущий на произвольный узел. Нужно создать его полную независимую копию. Звучит просто? Но без правильного подхода легко запутаться. В этой статье вы узнаете, как решить задачу копирования списка с произвольным указателем оптимально — за O(n) времени и O(1) дополнительной памяти, без использования HashMap.

Постановка задачи

Дан связанный список, каждый узел которого содержит:

• val — целочисленное значение;
• next — указатель на следующий узел;
• random — указатель на произвольный узел списка (может быть None).

Требуется создать глубокую копию списка. Это означает, что новый список должен состоять из совершенно новых узлов, сохранять все связи next и random, и не ссылаться ни на один узел исходного списка.

Базовое решение с HashMap

Интуитивно понятный подход — использовать словарь для отображения исходных узлов на их копии.

Идея

1. Первый проход: для каждого узла оригинала создаём копию и сохраняем пару оригинал -> копия в HashMap.
2. Второй проход: для каждого узла оригинала устанавливаем next и random у копии, используя словарь.

Реализация на Python

class Node:
    def __init__(self, val=0, next=None, random=None):
        self.val = val
        self.next = next
        self.random = random

def copy_random_list_hashmap(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:
        copy = old_to_new[cur]
        copy.next = old_to_new.get(cur.next)  # next может быть None
        copy.random = old_to_new.get(cur.random)  # random может быть None
        cur = cur.next
    
    return old_to_new[head]

Сложность

• Время: O(n) — два прохода по списку.
• Память: O(n) — под HashMap.

Это решение принимается на собеседованиях, но можно ли обойтись без дополнительной памяти?

Оптимальное решение без HashMap

Ключевая идея: вставить копии узлов сразу после оригиналов. Это создаёт естественную связь, позволяющую настроить random без словаря.

Пошаговый алгоритм

Шаг 1: Вставка копий

Проходим по списку и для каждого узла создаём его копию, помещая её между оригиналом и следующим узлом.

Пример: A -> B -> C превращается в A -> A' -> B -> B' -> C -> C'.

Шаг 2: Назначение random

Снова проходим по списку. Для каждого оригинального узла cur его копия находится в cur.next. Если cur.random не None, то cur.next.random = cur.random.next.

Почему это работает? Потому что cur.random.next — это копия того узла, на который указывает cur.random.

Шаг 3: Разделение списков

Восстанавливаем исходный список и извлекаем список копий.

Проходим по списку, для каждой пары оригинал-копия: original.next = copy.next, copy.next = copy.next.next (если есть).

Реализация на Python

def copy_random_list_optimal(head):
    if not head:
        return None
    
    # Шаг 1: вставляем копии между оригиналами
    cur = head
    while cur:
        copy = Node(cur.val)
        copy.next = cur.next
        cur.next = copy
        cur = copy.next
    
    # Шаг 2: устанавливаем random для копий
    cur = head
    while cur:
        if cur.random:
            cur.next.random = cur.random.next
        cur = cur.next.next
    
    # Шаг 3: разделяем списки
    dummy = Node(0)
    copy_tail = dummy
    cur = head
    while cur:
        copy = cur.next
        cur.next = copy.next
        copy_tail.next = copy
        copy_tail = copy
        cur = cur.next
    
    return dummy.next

Детальный разбор на примере

Исходный список: 1 -> 2 -> 3, где 1.random = 3, 2.random = 1, 3.random = 2.

1. После вставки копий: 1 -> 1' -> 2 -> 2' -> 3 -> 3'
2. Настройка random:
   • Для узла 1: 1.random = 3 -> 1'.random = 3.next = 3'
   • Для узла 2: 2.random = 1 -> 2'.random = 1.next = 1'
   • Для узла 3: 3.random = 2 -> 3'.random = 2.next = 2'
3. Разделение: исходный 1 -> 2 -> 3, копия 1' -> 2' -> 3'.

Сложность

• Время: O(n) — три прохода.
• Память: O(1) — не считая памяти под сами копии.

Практический вывод

Теперь вы знаете, как копировать список с произвольным указателем без использования дополнительной памяти. Этот приём часто встречается на собеседованиях. Прямо сейчас откройте LeetCode, найдите задачу «Copy List with Random Pointer» и решите её двумя способами: с HashMap и без. Закрепите навык, написав код на Python. Удачи!