CODEWITHSUNDEEP
c++recursionlinked-list
BabaSvoloch
BabaSvoloch

Reputation: 311

function with return type node* in conjunction with OOP in c++

I need to write a program that takes an instance of a linear linked list and removes all of the items in the list except for the last two items. I'm doing this in c++ using classes, so I'll have 3 files: main.cpp, list.h, and list.cpp. There can be no loops: I can use multiple functions but the traversal part has to be recursive.

I thought about it and what I concluded is this: I'll have to have one public function that I can call from main which will take no arguments, called void lastTwo(). I'll have another private function called node* lastTwo(node *& current, node *& tail) which will be called by lastTwo(), and it will traverse the list recursively and delete the nodes it touches until it reaches the second to last node in the list, and then it will return the address of that node.

Then, when it returns the address of the second to last node in the list, the public function lastTwo() will catch that address and set head equal to it.

The problem I'm having is that I need to do this in vi and compile and run from the command line, and I'm getting a segmentation fault even though I drew a pointer diagram and can't find a problem with my code.

I'm working on this on the student server at my university, and all of the implementation of the data structure except for these two functions have been written by my instructors, so they're all solid. Also, every time you run the a.out file, they've written it to generate a new, random, non-empty linked list, of at least 5 nodes.

I think the problem is related to the function having the return type "node*" , because I tried doing this in visual studio as well and it wouldn't let me have functions of type node*. But, I know that when you don't use classes and just put everything in one file, functions of type node* work.

Here is my list.h:

#include<iostream>

struct node
{
    int data;
    node* next;
};

class list
{
public:
    // these functions were already written by the school and included in the .o file
    list();
    ~list();
    void build();
    void display();

    // my functions
    void lastTwo();

private:
    node* head;
    node* tail;
    node* lastTwo(node *& current, node *& tail);
}

And list.cpp:

void list::lastTwo(){
    node* current = head;
    node * newHead = lastTwo(current, tail);
    head = newHead;
    delete newHead;
    head->next = tail;
}

node* lastTwo(node *& current, node *& tail){
    if(current->next == tail){
        return current;
    }
    else if(current->next != tail){
        node* temp = current;
        current = current->next;
        temp->next = NULL;
        delete temp;
        lastTwo(current, tail);
    }
    return NULL;
}

Any ideas on what might be the problem, and what the correct way to do this is, would be really appreciated! Thank you

Upvotes: 0

Views: 1649

Answers (2)

Jarod42
Jarod42

Reputation: 217418

You might use the following:

void list::lastTwo() {
     // Stop work with less than 2 items
    if (head == nullptr          // 0 items
        || head == tail          // 1 item
        || head->next == tail) { // 2 items
        return;
    }
    // pop_front()
    auto* next = head->next;
    delete head;
    head = next;
    // loop
    lastTwo();
}

Upvotes: 0

Michael Albers
Michael Albers

Reputation: 3779

Your problem happens when your recursion unwinds. Most of the calls to lastTwo happen in the else if. That base case is the if which returns current, but the call to lastTwo which triggered the base case is always going to return NULL when the else if ends.

Imagine this is your stack when the base case is reached:

 lastTwo // Base case, returns current, but the call below this doesn't do anything with it.
 lastTwo // returns null
 ...
 lastTwo // returns null

That NULL is used by the other lastTwo and you get your seg fault.

Upvotes: 1

Related Questions