在 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

假设我们有 IntList {1,2,3}，它实际上有这样的形式：

0 -> 1 -> 2 -> 3

然后我们调用reverse(root)，使得t_node与root具有相同的值（因此指向（0））。

Node* tmp = t_node->next;

所以 tmp 指向 (1)。

reverse(t_node->next);

假设这行得通，列表现在是 0->1->3->2

tmp->next = t_node;

所以现在 1->0。列表现在是一个循环，其他节点已经丢失了。

不清楚你打算这个函数做什么，但你一定是误解了什么。

编辑：当您不了解低级机制时，您正在尝试高级解决方案。

你的拷贝构造函数：

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

执行我们所说的 "shallow copy"；它复制指针成员，但不复制它们指向的东西。如果您的列表 A 如下所示：

0->1->2->3

然后调用 IntList B(A);，你会得到如下所示的内容：

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

如果您随后调用 A.pop_back() 和 B.pop_back()，您认为会发生什么？

更重要的是，你想做什么？你想知道如何编写递归函数，还是不再需要？

Answer 2

您的问题是，在 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;
        }
    }
}

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

在 C++ 中反转单链表

Reversing a singly-linked list in C++

c++

recursion

reverse

linked-list

data-structures