Recursively append the first node of Linear Linked List to the end

[SVcpp]

Hello,

Still a beginner to this recursive thing. I'm having a really hard time trying to solve this problem. I'm trying to append the first node of a linked list to the end of that same list. One additional bonus is I'm only able to use a function that will take a single pointer (head).

The biggest problem I'm having, is that I know each time a function is invoked on the stack the local variables that are stored won't have their same values and will be initialized to their original values. The reason this presents a problem for me is I thought a viable solution would be to grab the first node and separate it from the original list, "traverse" to the end of the list, and then append once I reach the end. However, two problems arise.

The first problem: If my base case is when head->next is NULL, how can I know when to grab and store the first node, use the recursive call to do the proper appendage & know when that node is the only node in the list, still using this as my base case? Is there another base case I should be aware of?

Second: If I'm recursively going through the list, then how can I access the first node to move it once I'm at the end since I'm at the end of the list.

I then realized that this was a problem too. I'm stuck because I'm mostly confused. I can't find the logic in this problem. could somebody please explain to me a viable way to approach this problem?

Currently, my approach would be to:
1. Check if the list coming in is empty, exit if true.
2. Check if there is only one node in the list
a. If this is the one and only node, exit
b. If this is the end of the list, append
3. return to the rest of the program



//writing this question helped me to find another solution :) Point out if this would be a good recursive approach? Ideas, comments, open to all! Thank you!

//assume a list is passed in, its size is random (>= 0)

int append_first_to_last(node * & to_append)
{
    node * tail = NULL;

    if(!to_append)
      return 0;

    //set a pointer to the last node
    if(!to_append->next){
       tail = to_append;
       return 1; //return to the invocation of this function
      }

    //traverse until the end of the list
    if(to_append->next)
        append_first_to_last(to_append->next);


//I'm stuck again, I can't find a solution past this point.
/* I know that I need to return to the very beginning of my list to append the node to tail
but I don't see how I can do that since I don't know where the beginning of the list is.
*/

This was an idea, but it was slowly proving wrong:

   //once the tail pointer is set to the end, hop into the else condition
   //this will append the first node to the last
       
       //if we are at the one and only node, set the pointer to NULL and exit

      /* check if there is more than one node in the list
      before making the change to the last node */
/*
      if(head->next)
        {
           node * first = head;
           head = head->next;
           first->next = NULL;
           tail->next
        }


    }//end else condition   
*/

}

[Momothegreat]

Nah man I have no idea what's going on.
I do have a question though, what is the data type of the list being passed in?

[SVcpp]

For simplicity, let's just say it's an integer list.

The original question is:

"Taking a list that is being passed in, grab the first node and append it after the last node. The function that must be used is" int first_last(node * & head) . You may not edit or alter the original function, but you may have more than one function. "

I'm pretty sure the solution will lie in a wrapper function.

[Momothegreat]

The only way I know how to handle something like that is if it was an array of integers and you were assigning values their position as they were read. Then you could just keep a counter of the size of the array, the first position would be 0 and the last would be n-1. Not sure if that helps at all in this situation though.

[cire]

Perhaps this will give you an idea:

// http://ideone.com/kaZwgC
#include <iostream>

template <typename T>
struct node
{
    T data ;
    node<T>* next = nullptr;

    node(const T& t) : data(t) {}
};

template <typename T>
void append(node<T>* list, node<T>* appendMe)
{
    if (!list->next)
        list->next = appendMe;
    else
        append(list->next, appendMe);
}

template <typename T>
void append(node<T>*& list, const T& item)
{
    if (list == nullptr)
    {
        list = new node<T>(item);
    }
    else
        append(list, new node<T>(item));
}

template <typename T>
void print(const node<T>* list)
{
    const node<T>* current = list;
    while (current)
    {
        std::cout << current->data << '\n';
        current = current->next;
    }
}

template <typename T>
void destroy(node<T>* list)
{
    node<T>* current = list;
    while (current)
    {
        node<T>* temp = current;
        current = current->next;
        delete temp;
    }

}

int main()
{
    node<int>* list = nullptr;
    for (int i = 1; i <= 10; ++i)
        append(list, i);

    print(list);
    destroy(list);
}

[SVcpp]

I really appreciate all of the code. It looks great. I'm trying to understand the code, but am having a bit of a hard time because I've never used a template before.

Also, it's reassuring to know that you are using multiple functions because I have been thinking about this for a few days now and I see no other way to solve it.

Can you explain why you use two "append" functions? Are you using the second as a wrapper function? How does the recursive call know to access the other function?

Also, this problem was supposed to be a challenge and for that reason I'm only allowed to have my primary function be int append (node * & list_to_append). For that reason, I'm thinking that I could still do something similar to what you have done, but start with only the primary function that calls the other append functions that would pass in the nodes?

Just so you know how much of a noob I am, I'll show you what kind of struct I would have made for something like this. I don't really understand all of the templates and certainly what the declaration on line 10 does.

 
struct node {

int data;
node * next;

 };

Thank you so much for your help! :)

[SVcpp]

@momothegreat

Thank you! Not in this particular instance would I be able to use something like that. However, I'll keep it in my back pocket just in case!

[SVcpp]

@cire

It seems like you know a lot about data structures. Any books you might want to recommend on Data Structures for beginners?