Карта дня, май, перетяжка
Карта дня, май, перетяжка
Карта дня, май, перетяжка

Задача на копирование списка

Аватар Типичный программист
Отредактировано

75К открытий75К показов
Задача на копирование списка

Есть однонаправленный список из структур. В нём random указывает на какой-то еще элемент этого же списка. Требуется написать функцию, которая копирует этот список с сохранением структуры (т.е. если в старом списке random первой ноды указывал на 4-ю, в новом списке должно быть то же самое — рандом первой ноды указывает на 4-ю ноду нового списка). O(n), константная дополнительная память + память под элементы нового списка. Нельзя сразу выделить память под все данные одник куском т.е. список должен быть честным, разбросанным по частям, а не единым блоком, как массив.

Вот один из вариантов решения. Делаем обход списка, создаём дубликаты узлов и вставляем их по next, получая 2*N элементов, каждый нечётный ссылается на свой дубликат. Делаем второй обход списка, в каждом чётном узле random = random.next. Делаем третий обход списка, в каждом узле next = next.next.

Есть ещё один вариант от Пашки Джиоева.

			Node *copyList(Node *head)
{
    for (Node* cur = head; cur != NULL; cur = cur->next) {
        Node* dup = (Node*)malloc(sizeof(Node));
        dup->data = cur->data;
        dup->next = cur->random;
        cur->random = dup;
    }
    Node* result = head->random;
    for (Node* cur = head; cur != NULL; cur = cur->next) {
        Node* dup = cur->random;
        dup->random = dup->next->random;
    }
    for (Node* cur = head; cur != NULL; cur = cur->next) {
        Node* dup = cur->random;
        cur->random = dup->next;
        dup->next = cur->next ? cur->next->random : NULL;
    }
    return result;
}
		
Следите за новыми постами
Следите за новыми постами по любимым темам
75К открытий75К показов