Copy a linked list
Solution 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).
Solution 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
Admin
Updated on June 04, 2022Comments
-
Admin almost 2 years
typedef struct Node { int data; Node *next; Node *other; }; Node *pHead;
pHead
is a singly linked list. Thenext
field points to the next element in the list. Theother
field may point to any other element (could be one of the previous nodes or one of the nodes ahead) in the list orNULL
.How does one write a copy function that duplicates the linked list and its connectivity? None of the elements (
next
andother
) in the new list should point to any element in the old list.