Copy Last Two Nodes C++

CJPowell27 · April 28, 2016

Hey guys, I was given a problem on my midterm to copy the last two nodes of a Doubly Linked List

and I honestly drew a blank on how to do it. I thought that I could possibly do it recursively but then

I realized I still had no idea what to do. Could someone possibly give an example as I can't find anything

good online. I realized that i would have to do something like:

node * temp = new node;

temp -> data = current -> data;

which would be making a temp node and setting its data but then I had no idea what to doto get there and

what to do from there.

I had another one where i was supposed to remove the last node if it hadn't appeared anywhere in the doubly

linked list but I don't even have start on that.

79wjd · April 28, 2016

I would do it iteratively rather than recursively.

void copyList (node * curr){ 
	if(curr == NULL) 
		return NULL;
	
	while(curr != NULL){ 
		node *temp = new node; 
		temp->data = curr->data; 
		temp->next = curr->next; 
		if(curr->next != NULL) 
			curr->next->prev = temp; 
		curr = curr->next; 
	}
	return; 
}

CJPowell27 · April 28, 2016

9 minutes ago, djdwosk97 said:

I would do it iteratively rather than recursively.


void copyList (node * curr){ 
	if(curr == NULL) 
		return NULL;
	
	while(curr != NULL){ 
		node *temp = new node; 
		temp->data = curr->data; 
		temp->next = curr->next; 
		if(curr->next != NULL) 
			curr->next->prev = temp; 
		curr = curr->next; 
	}
	return; 
}

Wouldn't that copy the whole list?

79wjd · April 28, 2016

13 minutes ago, CJPowell27 said:

Wouldn't that copy the whole list?

Oh, whoops, my bad, I somehow didn't notice you just wanted the last two.

Here's an idea, although it can be done in a more elegant manner. (This also doesn't make sure the list is at least two nodes long)

void copyLastTwo (node * curr){ 
	if(curr == NULL) 
		return NULL;
	
	while(curr != NULL){
                if(curr->next == NULL) 
		        break; 
	        curr = curr->next; 
	}

	for(int i=0; i<2; i++){
		node * temp = new node; 
		temp->data = curr->data; 
		if(i < 1){
			temp->prev = curr->prev;
		} else {
			temp->prev = NULL; 
		}
		temp->next = curr->next; 
		curr = curr->prev; 
	}

	return; 
}

CJPowell27 · April 28, 2016

13 minutes ago, djdwosk97 said:
Oh, whoops, my bad, I somehow didn't notice you just wanted the last two.

Here's an idea, although it can be done in a more elegant manner. (This also doesn't make sure the list is at least two nodes long)
void copyLastTwo (node * curr){ 
	if(curr == NULL) 
		return NULL;
	
	while(curr != NULL){
                if(curr->next == NULL) 
		        break; 
	        curr = curr->next; 
	}

	for(int i=0; i<2; i++){
		node * temp = new node; 
		temp->data = curr->data; 
		if(i < 1){
			temp->prev = curr->prev;
		} else {
			temp->prev = NULL; 
		}
		temp->next = curr->next; 
		curr = curr->prev; 
	}

	return; 
}

Oh hey that actually makes sense, there's probably a more elegant solution but that works thank you so much!

Now to figure out the other one

79wjd · April 28, 2016

1 minute ago, CJPowell27 said:

Oh hey that actually makes sense, there's probably a more elegant solution but that works thank you so much!

Now to figure out the other one

Well, since it's doubly-linked, there should be both head and tail sentinels. So, you can just copy tail and tail->prev (assuming tail->prev isn't null). But without knowing an exact implementation and how it would be called, getting something really elegant is a bit tricky. But, since elegance usually isn't tested for, simple is best imo since there's less things you're likely to overlook.

Something like this is a bit simpler (imo), but it lacks the expandability of the above, as if you wanted to copy the last ten nodes, in the first solution I posted you would just change the 2 to a 10 and the 1 to a 9, whereas this would require you to check if curr's->next->next->.....->next is null.

 
	void copyLastTwo (node *curr){
	       //check for at least one node
	       //if there's only one node, copy one node
	       
	        //at least two nodes by this point
	        while(curr-&gt;next-&gt;next != NULL) 
	               curr = curr-&gt;next; 
	 
	        //copy curr and curr-&gt;next 
	       return; 
	}