How would you write a recursive function that appends a second linked list to the end of the first linked list?  For
example, if the first linked list was:
list1 -> 1 -> 2 -> 3 -> NULL
And the second was:
list2 -> 4 -> 5 -> 6 -> NULL
How would you make it so the function would return a pointer to the first node of list1, with the nodes of list2
appended to the end of list2?  The function I have written so far only appends list two to the _last_ node of list1:

node_ptr append ( node_ptr list_1, node_ptr list_2 )
{
static node_ptr visit_ptr = list_1;

if ( visit_ptr->link == NULL )
{
return visit_ptr;
}
else // Recursive case.
{
return append ( list_1, list_2 );
}
}
###### Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

Commented:
You were nearly there!

node_ptr append ( node_ptr list_1, node_ptr list_2 )
{
// This is an automatic variable, so each time the
// function is called a new copy is made. When the
// function unwinds, the final return will return the
// original list_1 pointer
node_ptr visit_ptr = list_1;

if ( visit_ptr->link == NULL )
{
return visit_ptr;
}
else // Recursive case.
{
// This time the function is called with the next
return append ( visit_ptr->link, list_2 );
}
}
0
Commented:
You don't seem to need visit_ptr.
0
Author Commented:
Using the proposed answer, I got the exact same result:  list2 gets appended to list1, but all of the values in list1 get lost execept the last one.  After the call to append ( ), list1 should look like this:
1->2->3->4->5->6->NULL
3->4->5->6->NULL
0
Commented:
You do not want to return the results of the "append" call in the recursive case:  call append and then return "list_1" so that you do not lose the start-of-list pointer.
0
Commented:
First of all you really don't need a return value at all, but if you want a return value, it should just be list_1.  That's why I said you don't need visit_ptr at all.
0
Commented:
Try this... much simpler, and handler empty list for either list1 or list2.

node_ptr append (node_ptr list_1, node_ptr list_2) {
if (! list_2) {
// if no second list, then nothing to do
} else if (! list_1) {
// if no first list, the result is second list
list_1 = list_2;
} else {
// append second list to rest of first list
}
// return the combined list
return list_1;
}

This assumes you don't want to make a COPY of list_2 and append it to list 1.  If you do, then you need to copy the nodes. eg

node_ptr append_copy (node_ptr list_1, node_ptr list_2) {
if (! list_2) {
// if no second list, then nothing to do
} else if (! list_1) {
// create a new node
node_ptr copy = new node; // or whatever
// make it a copy of the first node of list_2
*copy = list_2;
// but with no tail yet
// get new item with the rest of list_2 appened
} else {
// append second list to rest of first list
}
// return the combined list
return list_1;
}

0
Commented:
Oops .. in append_copy above that should have said
// make it a copy of the first node of list_2
*copy = *list_2;
I missed the '*' infront of list_2

0
Commented:
Oops...slight oversight!

node_ptr append ( node_ptr list_1, node_ptr list_2 )
{
// This is an automatic variable, so each time the
// function is called a new copy is made. When the
// function unwinds, the final return will return the
// original list_1 pointer
node_ptr visit_ptr = list_1;

if ( visit_ptr->link == NULL )
{
}
else // Recursive case.
{
// This time the function is called with the next
}
return visit_ptr;

}
0
Commented:
Blondie .. that is effectively what the current proposed answer is.

Also note in my first function that the first test
if (! list_2)
is not strictly necessary, but saves some work for a simple case.  For the second example it is necessary, because the code dereferences the list_2 pointer.

0
Commented:
Ronslow:  I submitted an answer that was rejected because of a slight omission...I was simply clarifying that mistake...I didn't mean to tread on your toes...
0
Commented:
It wasn't my toes :-) .. just pointing out that that change has already been pointed out by mwalsh and nietod.

Of course, to be fair, I also need to point out to myself that not using visit_ptr in my code was also pointed out by nietod.

0
Author Commented:
RONSLOW, your function was correct but I unfortunately ended up giving the points to mwalsh because you submitted your suggestion as comment instead of an answer.  Sorry.
0
Commented:
I couldn't submit it as an answer because you did not reject mwalsh .. if you wish to accept another comment as an answer, you need to reject the current proposed answer so the other expert can submit there's.

If you reject mwalsh's proposed answer, then I can post mine and you can reward me approriately.

Or you can just accept mwalsh's answer and award him the points.

If you wis to split the points, put a message in Customer Service - Experts Exchange topic area (zero points) asking to do that and/or email linda@experts-exhcange.com and ask her about it.
0
Commented:
Hai Strider !

I have the solution for your problem

I SOLUTION : Just append list2 at the end of list1;

node_ptr append ( node_ptr list_1, node_ptr list_2 )
{
node_ptr  visit_ptr;
visit_ptr = list_1;

while (list_1->link != NULL)  /* Go to the last node of list1 */

return visit_ptr;
}

Note : Recursive function is not required here. You can directly use this.
This one is tested and it works fine.
Since the question is locked I cannot post this as answer.
I hope this is acceptable to you.
JESUS LOVES YOU - sganta
0
Commented:
Sganta, the answer must be recursive, that is a requirement in the question.  Admitidly that is not the best way to perform the task, but it is probably for a homework assignment.

You might want to leave out the Jesus stuff.  This is an international site and the majority of the world is not Christian.
0
Commented:
Hai Slider !

The earlier comment which I had sent is non recursive program.
Now I am sending recursive program with modifications of your program

node_ptr append ( node_ptr list_1, node_ptr list_2 )
{
static node_ptr visit_ptr = list_1;

if ( list_1->link == NULL )
{
return visit_ptr;
}
else // Recursive case.
{
return append ( list_1, list_2 );
}
}
This is tested and it works fine in the RECURSIVE cases.
I hope this is more than sufficient to you and acceptable to you.
Thanks and Regards - sganta

0
Commented:
Can I get points for my earlier recursive answer(s) ???

0
Commented:
To give me the points that you wanted to you need to reject the current proposed answer (y mwalsh) and let me submit an answer.

0
Author Commented:
Sorry, I already gave the points to someone else.  However, I give my thanks to you.  EE should change its design and let people choose who to reward right on the spot.
0
Commented:
The question appears to be ungradded.  mwalsh has proposed an answer, but you have not accepted it.  If you feel he gave the best answer you should grade it with an A-D.  If you feel someone else gave a better answer.  You should grade it with an F.  This will reopen the question and you can invite the other person to answer.  Then you can grade their answer.
0
Commented:
stride .. you have not given the pionts to anyone yet .. os now is your chance to award them as you want.  If there is an expert who you thinkg deserves the points (other than mwalsh) then reject his answer and post a comment stating which expert you would liek to reward.  Then that expert can post an answer and you can grade them appropriately (NOTE: giving higher grades do not cost you any more).

0
Author Commented:
RONSLOW, all right, I'll reject the current answer and you submit another one.
0
Commented:
// function returns a pointer to the combined list.
node_ptr append_copy (node_ptr list_1, node_ptr list_2) {
if (! list_2)
return list_1;
if (! list_1)
return list_2;

else

// return the combined list (eventually)
return list_1;
}

0

Experts Exchange Solution brought to you by

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Commented:
WHAT THE !!!!!

abesoft .. you have stolen my points !!!

This is very unethical behaviour !!

0
Commented:
RONSLOW

Actually, my answer is slightly different than yours.  In your recursive function you assign the result of the call to append to list_1->link.  This is an assignment for every level of recursion, were my solution just does one assignment when it finds the end of list 1.  I agree that both solutions work, and I also agree that I would never use a recursive function to do this operation in the first place (but that was the question).  But, the extra assignments are not needed.  However, if you still feel strongly about it, I would transfer the points.
0
Commented:
The decission of who deserves the points really belongs with strider.  He should have given the points to the expert he feels provided the most help.

If he felt that was abesoft, that is his right.  However, I suspect that he gave abesoft the points by mistake, not because he felt that was the best answer.
0
Commented:
That is what I feel as well .. that strider may not have realised that it was someone else who posted an answer after he had requested me to do so.

Perhaps abesoft also did not see the comment immediately before his answer of "RONSLOW, all right, I'll reject the current answer and you submit another one"?  If he _had_ seen it, and posted his answer anyway, then that would be fairly described as "poaching".

BTW: abesoft .. my soution also has only a single return point, rather than multiple ones (which is 'nicer' coding).  Also, it does not ignore the return value from the recursive call to 'append' (although not 'wrong' it does look a little odd).  Also I have less tests involved in my version .. so I could equally argue that you don't need to check list_1->link for null in every call .. it is not clear which one is most 'expensive'.

0
Author Commented:
I must've graded abesoft's response on accident, because I wanted to give the points to RONSLOW--I can't believe I did such a stupidity.  About, the function, I also found RONSLOW's to be the best, since it used the fewest assignment statements and it was a true recursive funtion.
0
Commented:
strider .. you may wish to contact linda@experts-exchange about this so she can correct the situation (eg. she might refund points to you so you can award some to me .. or whatever she feels is best).

Thanks.

0
Commented:
I am posting a question in this topic area to award points to RONSLOW for his answer.

Linda Gardner
Customer Service @ Experts Exchange
0
Author Commented:
There you go RONSLOW, and thanks linda.  :D
0
###### It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
C++

From novice to tech pro — start learning today.