Recursion on Linear Linked Lists

[chmstry]

Can anyone help me on these two recursion problems? I'm just practicing recursion on my own and I'm having trouble figuring out the solutions to these problems.

1. Remove every node in a linear linked list except the last two nodes (recursively)
2. Compare the first and last nodes' data in a linear linked list

My solutions below:

//remove all nodes except the last two nodes
int remove(node * & head)
{
    if(!head || !head->next || !head->next->next)
        return 0;

    node * temp;
    temp = head->next->next;
    head->next = temp;
    delete head;
    head = head->next;

    return remove(head);
}

//compare the first and last nodes' data
bool compare(node * head)
{
    if(!head)
        return false;

    compare(head->next);

    if(!head->next)
    {
        node * current = head;
    }

    if(current == head->data)
        return true;
}

I know my solution for the compare function is wrong; however, I'm not quite sure how to hold on to the values of the first and last nodes and compare them. Any comments, hints, or suggestions will be appreciated.

[Duthomhas]

You need to keep a copy of the last and before-last nodes, which translates to extra arguments to your function.

You could also just look down the list two nodes each function to see if you have reached the penultimate node or not.

[cire]

For state that needs to be realized on successive calls to recursive functions, pass it in the parameter list.

bool compare_head_with_tail(node* n, bool first_call = true, int data=0)
{
    if (!n)
        return false;

    if (first_call)
    {
        if (!(n->next))
            return true;  // head is tail

        return compare_head_with_tail(n->next, false, n->data);
    }

    if (!(n->next))
        return data == n->data ;

    return compare_head_with_tail(n->next, false, data) ;
}

Using a helper function can simplify the code by removing the need to detect some corner cases in the recursive function:

bool compare(node* current, int data)
{
    if (!(current->next))
        return current->data == data ;

    return compare(current->next, data);
}

bool compare_head_with_tail(node* list)
{
    if (!list)
        return false;

    if (!(list->next))
        return true ;

    return compare(list->next, list->data);
}

[Edit: This code is off-the-cuff and untested. OP beware!]

[chmstry]

Thank you so much, cire! I've been mulling over this problem for a few days now. I don't know why this was so difficult for me to understand. The use of a helper function really makes sense and puts what needs to be done in a clearer context. I've written similar functions to the ones you provided and it works perfectly. Thanks again!