Copy a linked list

Question

typedef struct Node
{
  int data;
  Node *next;
  Node *other;
};

Node *pHead;

pHead is a singly linked list. The next field points to the next element in the list. The other field may point to any other element (could be one of the previous nodes or one of the nodes ahead) in the list or NULL.

How does one write a copy function that duplicates the linked list and its connectivity? None of the elements (next and other) in the new list should point to any element in the old list.

Answer 1

Create a new node for every node in the old list, copy the corresponding data and make the next pointer of the nodes in the new list point to their successor in the new list, forgetting the other pointer for time being. At the time of creating a new node remember the mapping of node address something like:

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

In the second pass pass for every node in the new list consider its other pointer and find its corresponding node in the new list from the map and use it as the other pointer of this node (node in the new list).

Answer 2

Came across this. Hope it helps!

Citing one solution from this link, below.

1) Create the copy of 1 and insert it between 1 & 2, create the copy of 2 and insert it between 2 & 3.. Continue in this fashion, add the copy of N to Nth node

2) Now copy the arbitrary link in this fashion

 if original->arbitrary is not NULL
   original->next->arbitrary = original->arbitrary->next;  /*TRAVERSE TWO NODES*/
 else
   original->next->arbitrary=NULL;

This works because original->next is nothing but copy of original and Original->arbitrary->next is nothing but copy of arbitrary.

3) Now restore the original and copy linked lists in this fashion in a single loop.

 original->next = original->next->next;
 copy->next = copy->next->next;

4) Make sure that last element of original->next is NULL.

Sample code, Time Complexity O(N), Space Complexity 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;
}

Complete program is at http://gist.github.com/349630

Answer 3

I like the solution of Codaddict, but this would be my answer:

1. iterate over the linked list.
   a. store the data in an array (position i for the i'th node of course)
   b. replace data with i to create an id (this way you'll definitely know which node you are talking about)

2. create the 2nd linked list the size of the first (ignore the other pointer for now) *. maybe use a temporary array to find each node quickly

3. iterate over the first linked list. a. find out which id other points to (which is in that nodes data) b. recreate this link in the 2nd linked list (the temporary array could really help here)

4. iterate over both linked list simultaneously and replace the ids in data with the stored data

Of course you could collapse some processing and iterating here. But this would roughly be what I would do/think of.

Answer 4

What about something like

while(node != NULL)
{
    Node *duplicate = new Node();
    // copy data
    // add to the new list
    node = node->next;
}

Pretty much straight forward - just iterate them all and link appropriately.