c++ - 在 C++ 中反转单链表

Question

我在尝试递归反转单链表的实现时遇到问题。

我已经阅读了关于此过程的其他类似问题，但是，在我尝试在我自己的程序中实现此过程时，我遇到了问题。

这是我在下面的尝试(与随后的代码中呈现的内容略有不同):

注意:我的列表使用了一个root 指针，它不包含任何重要数据，仅用作引用列表中数据的地址。

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;
}

我在某处丢失了引用并在尝试显示列表时无休止地打印。我真的不知道我犯了什么错误，但怀疑这可能与我处理 root 的方式有关。

为了完整性，这里是整个程序(除了 reverse() 方法之外的所有功能)。

#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;
}

---

编辑:我修改了我的算法，我相信它在算法上是有效的，但在功能上它可能正在做一些导致内存问题的事情。我不确定为什么会这样，但就是这样:

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();
    }
}

事实上，如果我的 [] 运算符重载在此方法中起作用(出于某种原因它不是？)我可以取消 tmp 列表并只需将列表中的最后一个值直接引用为 this[size-1]。

这里有什么问题？

Answer 1

您的问题是，在 reverse() 之后，列表中的最后一个元素将指向根元素，而不是指向 null。一种解决方案可能是对该条件进行显式检查，这样您将获得:

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;
        }
    }
}

如果应该可以反转列表的子部分，那将不起作用。如果这是您需要的东西，那么您可能需要使用一个辅助函数来处理除第一个元素之外的所有元素。