为链表类模板添加一个将链表逆转的成员函数
时间: 2023-06-07 18:11:31 浏览: 49
好的,我可以帮您解答这个问题。为链表类模板添加一个将链表逆转的成员函数的实现可以参考以下代码:
```
template<typename T>
class LinkedList {
public:
struct Node {
T val;
Node* next;
Node(T x) : val(x), next(NULL) {}
};
Node* reverseList(Node* head) {
if (!head || !head->next) {
return head;
}
Node* p = reverseList(head->next);
head->next->next = head;
head->next = NULL;
return p;
}
};
```
这里是一个使用递归实现的链表逆转函数。如果链表为空或只有一个节点,直接返回原链表头即可。否则,递归处理链表中除头节点外的链表,将其逆转后返回,并将头节点接到逆转后链表的尾部。最后返回新的头节点,即原链表的尾节点。
您可以根据需要将此函数添加到您的链表类模板中。希望这个答案能对您有所帮助!
相关问题
设计一个单向链表类模板
好的,以下是一个简单的单向链表类模板的设计:
```c++
template<typename T>
class LinkedListNode {
public:
T data; // 存储节点数据
LinkedListNode<T>* next; // 存储指向下一个节点的指针
LinkedListNode(T data) {
this->data = data;
this->next = nullptr;
}
};
template<typename T>
class LinkedList {
private:
LinkedListNode<T>* head; // 存储指向链表头节点的指针
public:
LinkedList() {
this->head = nullptr;
}
~LinkedList() {
LinkedListNode<T>* current = this->head;
while (current != nullptr) {
LinkedListNode<T>* next = current->next;
delete current;
current = next;
}
}
void add(T data) {
LinkedListNode<T>* node = new LinkedListNode<T>(data);
if (this->head == nullptr) {
this->head = node;
} else {
LinkedListNode<T>* current = this->head;
while (current->next != nullptr) {
current = current->next;
}
current->next = node;
}
}
void remove(T data) {
LinkedListNode<T>* current = this->head;
LinkedListNode<T>* previous = nullptr;
while (current != nullptr) {
if (current->data == data) {
if (previous == nullptr) {
this->head = current->next;
} else {
previous->next = current->next;
}
delete current;
return;
}
previous = current;
current = current->next;
}
}
void print() {
LinkedListNode<T>* current = this->head;
while (current != nullptr) {
std::cout << current->data << " ";
current = current->next;
}
std::cout << std::endl;
}
};
```
该链表类具有添加节点、删除节点和打印链表等基本功能。其中,节点类`LinkedListNode`包含了节点数据和指向下一个节点的指针;链表类`LinkedList`包含了指向链表头节点的指针,以及添加、删除和打印链表的方法。
设计一个简单的单向链表类模板,并进行测试
好的,关于单向链表类模板的设计,我可以为您提供一些指导:
1. 首先需要定义一个节点类,节点包括两个成员变量:数据和指向下一个节点的指针。
2. 接着定义链表类,链表类包括一个成员变量:指向链表头节点的指针。还需要定义一些操作函数,如添加节点、删除节点、查找节点等等。
3. 最后,在测试代码中,您可以创建一个链表对象,执行各种操作函数,以确保链表类的功能正常。
以下是一个简单的单向链表类模板示例代码,希望可以帮助您:
```c++
template<typename T>
class LinkedList
{
public:
struct Node
{
T data;
Node* next;
Node(T& data) : data(data), next(nullptr) {}
};
LinkedList() : head(nullptr) {}
~LinkedList()
{
Node* current = head;
while (current != nullptr)
{
Node* next = current->next;
delete current;
current = next;
}
}
void addNode(T& data)
{
Node* newNode = new Node(data);
if (head == nullptr)
{
head = newNode;
}
else
{
Node* current = head;
while (current->next != nullptr)
{
current = current->next;
}
current->next = newNode;
}
}
bool removeNode(T& data)
{
Node* current = head;
if (head->data == data)
{
head = head->next;
delete current;
return true;
}
while (current->next != nullptr)
{
Node* next = current->next;
if (next->data == data)
{
current->next = next->next;
delete next;
return true;
}
current = next;
}
return false;
}
Node* findNode(T& data)
{
Node* current = head;
while (current != nullptr)
{
if (current->data == data)
{
return current;
}
current = current->next;
}
return nullptr;
}
private:
Node* head;
};
int main()
{
LinkedList<int> myList;
// 添加节点并测试
myList.addNode(1);
myList.addNode(2);
myList.addNode(3);
// 查找节点并测试
LinkedList<int>::Node* foundNode = myList.findNode(2);
if (foundNode != nullptr)
{
std::cout << "Found node containing data: " << foundNode->data << std::endl;
}
else
{
std::cout << "Node not found!" << std::endl;
}
// 删除节点并测试
bool success = myList.removeNode(2);
if (success)
{
std::cout << "Removed node successfully!" << std::endl;
}
else
{
std::cout << "Node not found!" << std::endl;
}
return 0;
}
```
希望这个示例能够帮助您实现一个简单的单向链表类模板。