Reversing a singly-linked list in C++

Question

I am having an issue with my attempt at recursively reversing my implementation of a singly-linked list.

I have read other similar questions regarding this process, however, in my attempt at implementing this process in my own program, I've come up short.

This is my attempt below (which is slightly different than what is presented in the code that follows thereafter):

Note: My list uses a root pointer which holds no significant data, and serves only as an address with which to reference data in the list.

void IntList::reverse(Node* t_node) {
    if(t_node == NULL) {
        reverse(root);
    } else

    if(t_node->next == NULL) {
        cout << "In (swapping): " << t_node->value << endl;
        root->next = t_node;
    } else {
        cout << "In: " << t_node->value << endl;
        Node* tmp = t_node->next;
        reverse(t_node->next);
        tmp->next = t_node;
    }
    return NULL;
}

I lose reference somewhere and print endlessly when trying to display the list. I am really at a loss as to what the error I've made is, but suspect it may have something to do with how I handle my root.

Here is the program in its entirety (all functioning apart from the reverse() methods) for completeness.

#ifndef INTLIST_H
#define INTLIST_H
#include<iostream>
using namespace std;
class IntList {
private:
   struct Node {
      int value;
      Node* next;
   };
   int size;
   Node* root;
   void destroy();
public:
   IntList() { root = new Node; root->next = 0; root-> value = 0; size = 0;}
   IntList(const IntList& list) { this->root = list.root; this->size = list.size; }
   ~IntList() {}
   void appendNode(int val);
   void insertNode(int pos, int val);
   void deleteNode(int pos);
   int searchNode(int val);
   int getSize() const;
   void print() const;
   Node* reverse(Node* t_node);
   int &operator[](int element) const;
   void pop_back();
   void pop_front();
   void push_back(int val);
   void push_front(int val);
};
void IntList::appendNode(int val) {
    push_back(val);
}
void IntList::insertNode(int pos, int val) {
    Node* tmp;
    Node* current = root;
    for(int i = 0; i < pos && current->next != NULL; i++) {
        current = current->next;
    }
    tmp = new Node;
    tmp->value = val;
    tmp->next = current->next;
    current->next = tmp;
    size++;
}
void IntList::deleteNode(int pos) {
    Node* tmp;
    Node* current = root;
    if(pos <= size-1) {
        for(int i = 0; i < pos; i++) {
            current = current->next;
        }
        tmp = current->next;
        current->next = tmp->next;
        delete tmp;
        size--;
    } else {
        cout << "ERROR: Out of range." << endl;
    }
}
int IntList::searchNode(int val) {
    int position = 0;
    Node* current = root->next;
    if(size != 0) {
        for(position = 0; position < size && current->value != val; position++) {
            current = current->next;
        }
    } else {
        cout << "ERROR: List is empty." << endl;
        position = -1;
    }
    return position;
}
int IntList::getSize() const {
    return size;
}
void IntList::print() const {
    Node* current = root->next;
    cout << "List: ";
    while(current != NULL) {
        cout << current->value << " ";
        current = current->next;
    }
    if(getSize() == 0) {
        cout << "Empty.";
    }
    cout << endl;
}
IntList::Node* IntList::reverse(Node* t_node) {
#define REVERSE
#ifndef REVERSE
    if(t_node == NULL) {
        reverse(root);
    } else

    if(t_node->next == NULL) {
        cout << "In (swapping): " << t_node->value << endl;
        root->next = t_node;
    } else {
        cout << "In: " << t_node->value << endl;
        Node* tmp = t_node->next;
        reverse(t_node->next);
        tmp->next = t_node;
    }
#endif //reverses list, but causes infinite loop in display
    return NULL;
}
int &IntList::operator[](int pos) const {
    Node* current = root->next;
    if(pos <= size-1) {
        for(int i = 0; i < pos; i++) {
            current = current->next;
        }
    } else {
        cout << "ERROR: Out of bounds.";
        current = NULL;
    }
    return current->value;
}
void IntList::pop_back() {
    deleteNode(size-1);
}
void IntList::pop_front() {
    deleteNode(0);
}
void IntList::push_back(int val) {
    insertNode(size, val);
}
void IntList::push_front(int val) {
    insertNode(0, val);
}
#endif

#ifndef LINKEDLIST_H
#define LINKEDLIST_H
#include<iostream>
using namespace std;
template<typename T>
class LinkedList {
private:
   struct Node {
      T value;
      Node* next;
   };
   int size;
   Node* root;
   void destroy();
public:
   LinkedList() { root = new Node; root->next = 0; root-> value = 0; size = 0;}
   LinkedList(const LinkedList &) {}
   ~LinkedList() {}
   void appendNode(T val);
   void insertNode(int pos, T val);
   void deleteNode(int pos);
   int searchNode(T val);
   int getSize() const;
   void print() const;
   void reverse(Node* t_node);
   int &operator[](int element) const;
   void pop_back();
   void pop_front();
   void push_back(T val);
   void push_front(T val);
};
template <typename T>
void LinkedList<T>::appendNode(T val) {
    push_back(val);
}
template <typename T>
void LinkedList<T>::insertNode(int pos, T val) {
    Node* tmp;
    Node* current = root;
    for(int i = 0; i < pos && current->next != NULL; i++) {
        current = current->next;
    }
    tmp = new Node;
    tmp->value = val;
    tmp->next = current->next;
    current->next = tmp;
    size++;
}
template <typename T>
void LinkedList<T>::deleteNode(int pos) {
    Node* tmp;
    Node* current = root;
    if(pos <= size-1) {
        for(int i = 0; i < pos; i++) {
            current = current->next;
        }
        tmp = current->next;
        current->next = tmp->next;
        delete tmp;
        size--;
    } else {
        cout << "ERROR: Out of range." << endl;
    }
}
template <typename T>
int LinkedList<T>::searchNode(T val) {
    int position = 0;
    Node* current = root->next;
    if(size != 0) {
        for(position = 0; position < size && current->value != val; position++) {
            current = current->next;
        }
    } else {
        cout << "ERROR: List is empty." << endl;
        position = -1;
    }
    return position;
}
template <typename T>
int LinkedList<T>::getSize() const {
    return size;
}
template <typename T>
void LinkedList<T>::print() const {
    Node* current = root->next;
    cout << "List: ";
    while(current != NULL) {
        cout << current->value << " ";
        current = current->next;
    }
    if(getSize() == 0) {
        cout << "Empty.";
    }
    cout << endl;
}
template <typename T>
void LinkedList<T>::reverse(Node* t_node) {
/*
    if(t_node == NULL) {
        reverse(root);
    } else

    if(t_node->next == NULL) {
        cout << "In (swapping): " << t_node->value << endl;
        root->next = t_node;
    } else {
        cout << "In: " << t_node->value << endl;
        Node* tmp = t_node->next;
        reverse(t_node->next);
        tmp->next = t_node;
    }
*/ //reverses list, but causes infinite loop in display
}
template <typename T>
int &LinkedList<T>::operator[](int pos) const {
    Node* current = root->next;
    if(pos <= size-1) {
        for(int i = 0; i < pos; i++) {
            current = current->next;
        }
    } else {
        cout << "ERROR: Out of bounds.";
        current = NULL;
    }
    return current->value;
}
template <typename T>
void LinkedList<T>::pop_back() {
    deleteNode(size-1);
}
template <typename T>
void LinkedList<T>::pop_front() {
    deleteNode(0);
}
template <typename T>
void LinkedList<T>::push_back(T val) {
    insertNode(size, val);
}
template <typename T>
void LinkedList<T>::push_front(T val) {
    insertNode(0, val);
}
#endif

//test driver
int main() {
    IntList i_list;
    int n;

    cout << "Appending node: value = " << 0 << endl;
    i_list.appendNode(0);
    i_list.print();
    cout << endl;

    n = 5;
    cout << "Inserting nodes (at their values). Node values = { ";
    for(int i = 0; i < n; i++) {
        cout << i << " ";
        i_list.insertNode(i,i);
    }
    cout << "}" << endl;
    i_list.print();
    cout << endl;

    cout << "Deleting node at position: " << i_list.getSize()-1 << endl;
    i_list.deleteNode(i_list.getSize()-1);
    i_list.print();
    cout << endl;

    cout << "Searching for value: " << 3 << endl;
    cout << "Found at: " << i_list.searchNode(3) << endl;
    cout << endl;

    i_list.print();
    cout << "List size: " << i_list.getSize() << endl;
    cout << endl;

    n = 3;
    cout << "Calling node at list[" << n << "]: " << i_list[n] << endl;
    cout << endl;

    i_list.print();
    cout << "Deleting node from back position." << endl;
    i_list.pop_back();
    i_list.print();
    cout << endl;

    i_list.print();
    cout << "Deleting node from front position." << endl;
    i_list.pop_front();
    i_list.print();
    cout << endl;

    n = 9;
    i_list.print();
    cout << "Adding node (value = " << n << ") to back position." << endl;
    i_list.push_back(n);
    i_list.print();
    cout << endl;

    n = 8;
    i_list.print();
    cout << "Adding node (value = " << n << ") to front position." << endl;
    i_list.push_front(n);
    i_list.print();
    cout << endl;

    i_list.print();
    cout << "Copying list to new list." << endl;

    IntList t_list(i_list);
    cout << endl;

    cout << "List copy:" << endl;
    t_list.print();
    cout << endl;

    /*
     * Showing functionality transfers over to LinkedList template class
     * generally, for primitive data types (lacks absolutely generality
     * for data which can't be passed directly to cout).
     */
    cout << "List functionality transfers generally to LinkedList class:" << endl;
    LinkedList<int> int_list;
    LinkedList<double> double_list;
    LinkedList<char> char_list;

    cout << "Appending nodes:" << endl;

    n = 5;
    for(int i = 0; i < n; i++){
        int_list.appendNode(i);
    }
    int_list.print();

    n = 5;
    for(int i = 0; i < n; i++){
        double_list.appendNode(i+0.1);
    }
    double_list.print();

    n = 5;
    for(int i = 0; i < n; i++){
        char_list.appendNode('A' + i);
    }
    char_list.print();

    cout << "Removing nodes:" << endl;

    n = 5;
    for(int i = 0; i < n; i++){
        int_list.pop_back();
    }
    int_list.print();

    n = 5;
    for(int i = 0; i < n; i++){
        double_list.pop_back();
    }
    double_list.print();

    n = 5;
    for(int i = 0; i < n; i++){
        char_list.pop_back();
    }
    char_list.print();

    return 0;
}

---

EDIT: I've revised my algorithm, and I believe it works algorithmically, but functionally it may be doing something which is causing a memory issue. I'm not sure as to why that may be, but here it is:

void IntList::reverse() {
    IntList tmp(*this);
    int list_size = size;
    for(int i = 0; i < list_size; i++) {
        this->insertNode(i, tmp[tmp.getSize()-1]);
        this->pop_back();
        tmp.pop_back();
    }
}

In fact, if my [] operator overload were functioning within this method (which for some reason it is not?) I could do away with the tmp list and just reference the last value in the list directly as this[size-1].

What is the issue here?

Answer 1

Your problem is that after the reverse() the last element in your list will point to the root element instead of pointing to null. One solution could be an explicit check for that condition so you would get:

void IntList::reverse(Node* t_node) {
    if(t_node == NULL) {
        reverse(root);
        return;
    }

    if(t_node->next == NULL) {
        cout << "In (swapping): " << t_node->value << endl;
        root->next = t_node;
    } else {
        cout << "In: " << t_node->value << endl;
        Node* tmp = t_node->next;
        reverse(t_node->next);
        // If this node was the first node it will now be the last
        if (t_node == root) {
            tmp->next = NULL;
        } else {
            tmp->next = t_node;
        }
    }
}

That doesn't work if it should be possible to reverse a subpart of the list though. If that is something you need, then you probably need to use a helper function which handles all elements but the first one.

Answer 2

Suppose we have the IntList {1,2,3}, which actually has this form:

0 -> 1 -> 2 -> 3

Then we call reverse(root), so that t_node has the same value as root (and therefore points to (0)).

Node* tmp = t_node->next;

So tmp points to (1).

reverse(t_node->next);

Suppose this works, and the list is now 0->1->3->2

tmp->next = t_node;

So now 1->0. The list is now a loop, and the other nodes have been lost.

It is not clear what you intended this function to do, but you must have misunderstood something.

EDIT: You are attempting a high-level solution when you do not understand the low-level mechanics.

Your copy constructor:

IntList(const IntList& list) { this->root = list.root; this->size = list.size; }

performs what we call a "shallow copy"; it copies the pointer members, but not the things they point to. If you have a list A that looks like this:

0->1->2->3

and then call IntList B(A);, you'll get something that looks like this:

   0
   |
   v
0->1->2->3

If you then call A.pop_back() and B.pop_back(), what do you think will happen?

And more to the point, what are you trying to do? Do you want to know how to write a recursive function, or is that no longer necessary?