Sunday, March 24, 2019

c++ - Copying a linked list to a reference to a linkedlist




I have been assigned to pass a pointer to a linked list and copy that to a new list passed as a pointer to a linked list, and copy it recursively. I receive a segmentation fault when trying to copy the very first item.



I've tried every combination of pointer and reference I can think of while maintaining the program requirements of the function prototype:
void duplicate(node * head, node *& newHead)



 #include 
#include "supplied.o"

using namespace std;


struct node
{
int data;
node * next;
};

int main()
{
node * head = NULL;
build(head); // supplied function initializes list

newHead = NULL;
duplicate (head, newHead);
}

void duplicate (node * head, node*& newHead)
{
node * iterator1 = NULL;
node * iterator2 = new Node;
node * iterator2 = newHead;
iterator2->data = iterator1->data; //error occurs here

// program will continue to copy list recursively
}

void build (node *& head) //cannot see this function; provided via "supplied.o"
{
}


the error occurs because the function is unable to access iterator2->data. Iterator1->data can be accessed and even printed without problem.


Answer




Just create a new node, then copy the data, then recurse with the next nodes. Take care of null pointers. That's all.



duplicate(const node*head, node* &newhead)
{
if(head) {
// copy a valid node
newhead = new node; // allocate a new node
newhead->data = head->data; // copy the data
duplicate(head->next, newhead->next); // recurse on the next node
} else

// in case of null pointer: terminate recursion
newhead = nullptr;
}


Now, consider what happens step-by-step if you call duplicate with a long list and convince yourself that it actually does what you want.


No comments:

Post a Comment

plot explanation - Why did Peaches' mom hang on the tree? - Movies & TV

In the middle of the movie Ice Age: Continental Drift Peaches' mom asked Peaches to go to sleep. Then, she hung on the tree. This parti...