Скопировать связанный список
typedef struct Node
{
int data;
Node *next;
Node *other;
};
Node *pHead;
pHead
является односвязным списком. Поле next
указывает на следующий элемент в списке. Поле other
может указывать на любой другой элемент (может быть один из предыдущих узлов или один из узлов впереди) в списке или NULL
.
Как написать функцию копирования, которая дублирует связанный список и его связь? Ни один из элементов (next
и other
) в новом списке не должен указывать на любой элемент старого списка.
Ответы
Ответ 1
Создайте новый node для каждого node в старом списке, скопируйте соответствующие данные и сделайте следующий указатель узлов в новой точке списка своим преемником в новом списке, забудьте указатель other
на время. Во время создания нового node помните, что отображение node адресует что-то вроде:
Old_list New_list
-------------------
0x123 0x345 [ addresses of the first node]
0xabc 0xdef [ addresses of the second node]
...
Во втором проходе для каждого node в новом списке рассмотрим его указатель other
и найдите его соответствующий node в новом списке с карты и используйте его как указатель other
этого node (node в новом списке).
Ответ 2
Перешел этот. Надеюсь, это поможет!
Ссылаясь на одно решение из этой ссылки ниже.
1) Создайте копию 1 и вставьте ее между 1 и 2, создайте копию 2 и вставьте ее между 2 и 3. Продолжайте таким образом, добавьте копию N в Nth node
2) Теперь скопируйте произвольную ссылку таким образом
if original->arbitrary is not NULL
original->next->arbitrary = original->arbitrary->next; /*TRAVERSE TWO NODES*/
else
original->next->arbitrary=NULL;
Это работает, потому что original- > 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
Ответ 3
Мне нравится решение Codaddict, но это был бы мой ответ:
-
перебрать связанный список.
а. сохраняйте данные в массиве (позиция я для i'th node, конечно)
б. замените данные на i, чтобы создать идентификатор (таким образом, вы определенно знаете, о каком node вы говорите)
-
создайте 2-й связанный список размером первого (пока игнорируйте другой указатель)
*. возможно, используйте временный массив, чтобы быстро найти каждый node
-
перебирать первый связанный список.
а. узнайте, какой id других точек (который находится в данных этих узлов)
б. воссоздайте эту ссылку во втором связанном списке (временный массив может действительно помочь здесь)
-
итерация по обоим связанным спискам одновременно и замена идентификаторов в данных на сохраненные данные
Конечно, вы можете свернуть обработку и итерацию здесь. Но это будет примерно то, что я буду делать/думать.