Solved

Appending a Linked List

Posted on 1998-05-10
31
231 Views
Last Modified: 2012-05-04
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 )
     {
          visit_ptr->link = list_2;
          return visit_ptr;
     }
     else // Recursive case.
     {
          visit_ptr = visit_ptr->link;
          return append ( list_1, list_2 );
     }
}
0
Comment
Question by:strider031598
  • 11
  • 6
  • 5
  • +5
31 Comments
 
LVL 1

Expert Comment

by:Blondie050798
Comment Utility
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 )
     {
          visit_ptr->link = list_2;
          return visit_ptr;
     }
     else // Recursive case.
     {
          // This time the function is called with the next
          // link in the chain.
          return append ( visit_ptr->link, list_2 );
     }
}
0
 
LVL 22

Expert Comment

by:nietod
Comment Utility
You don't seem to need visit_ptr.
0
 

Author Comment

by:strider031598
Comment Utility
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
Instead of like this:
     3->4->5->6->NULL
0
 

Expert Comment

by:mwalsh111097
Comment Utility
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
 
LVL 22

Expert Comment

by:nietod
Comment Utility
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
 
LVL 10

Expert Comment

by:RONSLOW
Comment Utility
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
        list_1->link = append(list_1->link, list_2);
    }
    // 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
        copy->link = NULL;
        // get new item with the rest of list_2 appened
        list_1 = append_copy(copy,list_2->link);
    } else {
        // append second list to rest of first list
        list_1->link = append_copy(list_1->link, list_2);
    }
    // return the combined list
    return list_1;
}

0
 
LVL 10

Expert Comment

by:RONSLOW
Comment Utility
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
 
LVL 1

Expert Comment

by:Blondie050798
Comment Utility
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 )
     {
          visit_ptr->link = list_2;
     }
     else // Recursive case.
     {
          // This time the function is called with the next
          // link in the chain.
          append ( visit_ptr->link, list_2 );
     }
     return visit_ptr;

}
0
 
LVL 10

Expert Comment

by:RONSLOW
Comment Utility
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
 
LVL 1

Expert Comment

by:Blondie050798
Comment Utility
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
 
LVL 10

Expert Comment

by:RONSLOW
Comment Utility
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 Comment

by:strider031598
Comment Utility
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
 
LVL 10

Expert Comment

by:RONSLOW
Comment Utility
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
 
LVL 4

Expert Comment

by:sganta
Comment Utility
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 */
             list_1 = list_1->link;

         list_1->link = list_2;   /* link to the list 2 */
   
         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
 
LVL 22

Expert Comment

by:nietod
Comment Utility
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
How your wiki can always stay up-to-date

Quip doubles as a “living” wiki and a project management tool that evolves with your organization. As you finish projects in Quip, the work remains, easily accessible to all team members, new and old.
- Increase transparency
- Onboard new hires faster
- Access from mobile/offline

 
LVL 4

Expert Comment

by:sganta
Comment Utility
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 )
         {
              list_1->link = list_2;
              return visit_ptr;
         }
         else // Recursive case.
         {
              list_1 = list_1->link;
              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
 
LVL 10

Expert Comment

by:RONSLOW
Comment Utility
Can I get points for my earlier recursive answer(s) ???

0
 
LVL 10

Expert Comment

by:RONSLOW
Comment Utility
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 Comment

by:strider031598
Comment Utility
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
 
LVL 22

Expert Comment

by:nietod
Comment Utility
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
 
LVL 10

Expert Comment

by:RONSLOW
Comment Utility
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 Comment

by:strider031598
Comment Utility
RONSLOW, all right, I'll reject the current answer and you submit another one.
0
 
LVL 2

Accepted Solution

by:
abesoft earned 100 total points
Comment Utility
// 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;

    if (list_1->link == NULL)
        list_1->link = list_2;
    else
        append (list_1->link, list_2);

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

0
 
LVL 10

Expert Comment

by:RONSLOW
Comment Utility
WHAT THE !!!!!

abesoft .. you have stolen my points !!!

This is very unethical behaviour !!

0
 
LVL 2

Expert Comment

by:abesoft
Comment Utility
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
 
LVL 22

Expert Comment

by:nietod
Comment Utility
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
 
LVL 10

Expert Comment

by:RONSLOW
Comment Utility
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 Comment

by:strider031598
Comment Utility
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
 
LVL 10

Expert Comment

by:RONSLOW
Comment Utility
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
 
LVL 7

Expert Comment

by:linda101698
Comment Utility
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 Comment

by:strider031598
Comment Utility
There you go RONSLOW, and thanks linda.  :D
0

Featured Post

Enabling OSINT in Activity Based Intelligence

Activity based intelligence (ABI) requires access to all available sources of data. Recorded Future allows analysts to observe structured data on the open, deep, and dark web.

Join & Write a Comment

What is C++ STL?: STL stands for Standard Template Library and is a part of standard C++ libraries. It contains many useful data structures (containers) and algorithms, which can spare you a lot of the time. Today we will look at the STL Vector. …
IntroductionThis article is the second in a three part article series on the Visual Studio 2008 Debugger.  It provides tips in setting and using breakpoints. If not familiar with this debugger, you can find a basic introduction in the EE article loc…
The viewer will learn how to pass data into a function in C++. This is one step further in using functions. Instead of only printing text onto the console, the function will be able to perform calculations with argumentents given by the user.
The viewer will learn how to use the return statement in functions in C++. The video will also teach the user how to pass data to a function and have the function return data back for further processing.

762 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

12 Experts available now in Live!

Get 1:1 Help Now