Копирование связного списка с random указателями

Решение

Описание задачи

Нужно скопировать связный список, где каждый узел имеет два указателя: next (следующий узел в списке) и random (произвольный узел). Требование - O(n) время и константная O(1) дополнительная память (не считая выходного списка).

Подход: Алгоритм трёх проходов

Ключевая идея - вместо хеш-таблицы для хранения маппинга узлов используем манипуляцию со ссылками прямо в исходном списке.

Этапы алгоритма

1. Первый проход: Создаём копию каждого узла и вставляем его сразу после оригинала (1->1'->2->2'->3->3')
2. Второй проход: Устанавливаем random указатели копий (используя связь original->copy через next)
3. Третий проход: Разделяем исходный и копированный списки

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

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

def copyRandomList(head):
    if not head:
        return None
    
    # Этап 1: Вставляем копии узлов
    current = head
    while current:
        copy = Node(current.val)
        copy.next = current.next
        current.next = copy
        current = copy.next
    
    # Этап 2: Устанавливаем random указатели в копиях
    current = head
    while current:
        if current.random:
            current.next.random = current.random.next
        current = current.next.next
    
    # Этап 3: Разделяем списки
    current = head
    copy_head = head.next
    
    while current:
        copy_node = current.next
        current.next = copy_node.next
        if copy_node.next:
            copy_node.next = copy_node.next.next
        current = current.next
    
    return copy_head

Пошаговый пример

Исходный список: 1->2->3 (random: 1->3, 2->1, 3->2)

После этапа 1:

1->1'->2->2'->3->3'

После этапа 2 (установка random в копиях):

1->1'(random->3')->2->2'(random->1')->3->3'(random->2')

После этапа 3 (разделение):

Исходный: 1->2->3
Копия:    1'->2'->3' (с тем же структурой random)

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

class Node {
    constructor(val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}

function copyRandomList(head) {
    if (!head) return null;
    
    // Этап 1: Вставляем копии
    let current = head;
    while (current) {
        const copy = new Node(current.val);
        copy.next = current.next;
        current.next = copy;
        current = copy.next;
    }
    
    // Этап 2: Устанавливаем random
    current = head;
    while (current) {
        if (current.random) {
            current.next.random = current.random.next;
        }
        current = current.next.next;
    }
    
    // Этап 3: Разделяем
    current = head;
    const copyHead = head.next;
    
    while (current) {
        const copy = current.next;
        current.next = copy.next;
        if (copy.next) {
            copy.next = copy.next.next;
        }
        current = current.next;
    }
    
    return copyHead;
}

Анализ сложности

Временная сложность: O(n)

• Три отдельных прохода по списку, каждый O(n)
• Итого: 3n = O(n)

Пространственная сложность: O(1)

• Используем только несколько переменных для итерации
• Манипулируем существующими указателями, не создаём дополнительные структуры
• Выходной список не считается в анализе сложности

Альтернативный подход: С хеш-таблицей (проще, но O(n) память)

def copyRandomListWithHash(head):
    if not head:
        return None
    
    mapping = {}  # original -> copy
    
    # Проход 1: Создаём копии всех узлов
    current = head
    while current:
        mapping[current] = Node(current.val)
        current = current.next
    
    # Проход 2: Устанавливаем next и random
    current = head
    while current:
        copy = mapping[current]
        copy.next = mapping.get(current.next)
        copy.random = mapping.get(current.random)
        current = current.next
    
    return mapping[head]

Этот подход проще понять и реализовать, но нарушает требование O(1) памяти.

Тестирование

def test_copy_random_list():
    # Создаём список 1->2->3
    head = Node(1)
    head.next = Node(2)
    head.next.next = Node(3)
    
    # Устанавливаем random: 1->3, 2->1, 3->2
    head.random = head.next.next
    head.next.random = head
    head.next.next.random = head.next
    
    # Копируем
    copy = copyRandomList(head)
    
    # Проверяем структуру
    assert copy.val == 1
    assert copy.next.val == 2
    assert copy.next.next.val == 3
    assert copy.random.val == 3
    assert copy.next.random.val == 1
    assert copy.next.next.random.val == 2

Ключевые особенности решения

• Инновативный подход: Используем исходный список как временное хранилище маппинга
• Восстановление структуры: Критично правильно разделить списки на этапе 3
• Обработка null: random может быть null - проверяем перед доступом
• Сложность реализации: Требует тщательной отработки, но демонстрирует глубокое понимание указателей