Скопируйте связанный список
typedef struct Node
{
int data;
Node *next;
Node *other;
};
Node *pHead;
pHead отдельно связанный список. next поле указывает на следующий элемент в списке. other поле может указать на любой другой элемент (мог быть один из предыдущих узлов или один из узлов вперед) в списке или NULL.
Как каждый пишет функцию копии, которая копирует связанный список и его возможность соединения? Ни один из элементов (next и other) в новом списке должен указать на любой элемент в старом списке.
3 ответа
Создайте новый узел для каждого узла в старом списке, скопируйте соответствующие данные и сделайте так, чтобы следующий указатель узлов в новом списке указывал на их преемника в новом списке, забыв об указателе other пока. Во время создания нового узла запомните отображение адреса узла примерно так:
Old_list New_list
-------------------
0x123 0x345 [ addresses of the first node]
0xabc 0xdef [ addresses of the second node]
...
На втором проходе для каждого узла в новом списке рассмотрите его указатель other и найдите соответствующий ему узел в новом list из карты и используйте его как указатель other этого узла (узел в новом списке).
Обнаружил это . Надеюсь, поможет!
Ссылаясь на одно решение из этой ссылки ниже.
1) Создайте копию 1 и вставьте ее между 1 и 2, создайте копию 2 и вставьте ее между 2 и 3 .. Продолжайте таким же образом, добавьте копию N к N-му узлу
2) Теперь скопируйте произвольную ссылку таким образом
if original->arbitrary is not NULL
original->next->arbitrary = original->arbitrary->next; /*TRAVERSE TWO NODES*/
else
original->next->arbitrary=NULL;
. Это работает, потому что original-> next - это не что иное, как копия оригинала, а Original-> random-> next - не что иное, как копия произвольного.
3) Теперь восстановите исходные и скопируйте связанные списки таким образом за один цикл.
original->next = original->next->next;
copy->next = copy->next->next;
4) Убедитесь, что последний элемент original-> next равен NULL.
Пример кода, сложность времени O (N), сложность пространства O (1)
pNode copy_list(pNode head) {
// pre-condition: node->other either points into the list or NULL
if (!head) return NULL;
pNode node = head, copied = NULL, cnode = NULL;
for ( ; node; node = node->next->next) {
// make copy
cnode = newnode(node->next, node->data);
cnode->other = node->other;
if (node == head)
copied = cnode;
// insert the copy between originals
node->next = cnode;
// node -> cnode -> (orig)node->next
}
for (node = head; node && node->next;
node = node->next->next /* only original nodes */)
if (node->other)
node->next->other = node->other->next;
else
node->next->other = NULL;
// restore lists
node = head; cnode = copied;
for ( ; cnode && cnode->next; node = node->next, cnode = cnode->next) {
node->next = node->next->next;
cnode->next = cnode->next->next;
}
node->next = NULL;
return copied;
}
Полная программа находится по адресу http://gist.github.com/349630
Мне нравится решение Codaddict, но это был бы мой ответ:
итерация по связанному списку.
a. хранить данные в массиве (позиция i для i-го узла, конечно)
b. замените данные на i, чтобы создать идентификатор (так вы точно будете знать, о каком узле идет речь)создайте второй связный список размером с первый (пока игнорируйте другой указатель) *. возможно, использовать временный массив для быстрого поиска каждого узла
итерация по первому связанному списку. a. выяснить, на какой идентификатор указывает другой (который находится в данных этого узла) b. воссоздать эту ссылку во втором связном списке (временный массив может здесь очень помочь)
просмотреть оба связных списка одновременно и заменить идентификаторы в данных на сохраненные данные
Конечно, вы можете свернуть здесь некоторую обработку и итерацию. Но примерно так я бы поступил/подумал.