Скопировать связанный список - PullRequest
Новая
       16

Скопировать связанный список

15 голосов
/ 11 февраля 2010 
typedef struct Node
{
  int data;
  Node *next;
  Node *other;
};

Node *pHead;

pHead - односвязный список. Поле next указывает на следующий элемент в списке. Поле other может указывать на любой другой элемент (может быть одним из предыдущих узлов или одним из узлов впереди) в списке или NULL.

Как написать функцию копирования, которая дублирует связанный список и его связность? Ни один из элементов (next и other) в новом списке не должен указывать на какой-либо элемент в старом списке.

Ответы [ 3 ]

8 голосов
/ 11 февраля 2010

Создайте новый узел для каждого узла в старом списке, скопируйте соответствующие данные и сделайте так, чтобы следующий указатель узлов в новом списке указывал на их преемника в новом списке, забыв на время указатель other. Во время создания нового узла запомните отображение адреса узла примерно так: 

Old_list   New_list
------------------- 
0x123      0x345     [ addresses of the first node]
0xabc      0xdef     [ addresses of the second node]
...

Во втором проходе для каждого узла в новом списке рассмотрите его указатель other и найдите соответствующий ему узел в новом списке на карте и используйте его как указатель other этого узла (узла в новом список).

7 голосов
/ 11 февраля 2010

Наткнулся на это . Надеюсь, это поможет!

Ссылаясь на одно решение по этой ссылке, ниже.

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;

Это работает, потому что оригинал-> следующий - не что иное, как копия оригинала, а Оригинал-> произвольный-> следующий - только копия произвольного.

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

0 голосов
/ 30 марта 2010

Мне нравится решение Codaddict, но это будет мой ответ:

  1. перебрать связанный список.
    а. сохранить данные в массиве (позиция i для i-го узла, конечно)
    б. замените данные на i, чтобы создать идентификатор (таким образом, вы точно будете знать, о каком узле вы говорите)

  2. создайте 2-й связанный список размером с первый (пока игнорируйте другой указатель) *. возможно использовать временный массив для быстрого поиска каждого узла

  3. итерация по первому связанному списку. а. выяснить, на какой идентификатор указывают другие (которые находятся в данных этих узлов) б. воссоздайте эту ссылку во втором связанном списке (временный массив здесь действительно может помочь)

  4. итерация по обоим связанным спискам одновременно и замена идентификаторов в данных на сохраненные данные

Конечно, вы можете свернуть некоторую обработку и итерацию здесь. Но это примерно то, что я буду делать / думать.

...