[已解决]单链表逆置

yangzhixiaohuli · 发表于 2024-10-18 17:24:24

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

将单链表倒置，要求只利用原表的存储空间。

原单链表如下所示：图片.png

倒置后的单链表应为：

1.png

输入格式:
第一行输入n的值，表示单链表的元素个数。
第二行输入n个整数值，作为单链表的各元素值。

输出格式:
输出倒置后的单链表的各元素值，各元素值之间用空格分隔。

输入样例1:
4
2 4 6 8

输出样例1:
8 6 4 2

输入样例2:
7
1 3 5 7 9 11 13

输出样例2:
13 11 9 7 5 3 1

4
2 4 6 8
8 6 4 2

这题用C++怎么做

最佳答案

月排行榜 / 总排行榜

FishC

2024-10-18 17:24:35

要在C++中实现单链表逆置，且只利用原链表的存储空间，可以通过指针操作来改变链表的节点指向。以下是一个简单的实现：

#include <iostream>
struct Node {
int data;
Node* next;
Node(int val) : data(val), next(nullptr) {}
};
class LinkedList {
public:
Node* head;
LinkedList() : head(nullptr) {}
void append(int val) {
if (!head) {
head = new Node(val);
} else {
Node* temp = head;
while (temp->next) {
temp = temp->next;
}
temp->next = new Node(val);
}
}
void reverse() {
Node* prev = nullptr;
Node* current = head;
Node* next = nullptr;
while (current) {
next = current->next; // Save next
current->next = prev; // Reverse current node's pointer
prev = current; // Move pointers one position forward
current = next;
}
head = prev;
}
void print() const {
Node* temp = head;
while (temp) {
std::cout << temp->data;
if (temp->next) {
std::cout << " ";
}
temp = temp->next;
}
std::cout << "\n";
}
};
int main() {
int n;
std::cin >> n;
LinkedList list;
for (int i = 0; i < n; ++i) {
int val;
std::cin >> val;
list.append(val);
}
list.reverse();
list.print();
return 0;
}

复制代码

### 代码说明：
- **Node 结构体**：用于表示链表节点，包含数据和指针用于指向下一个节点。
- **LinkedList 类**：用于管理链表，包括添加新节点 (`append` 方法)、反转链表 (`reverse` 方法) 和打印链表 (`print` 方法) 的功能。
- **reverse 方法**：通过改变节点的指向来逆置链表，不需要额外的存储空间。
- **main 函数**：负责输入并调用上述功能进行链表处理。

通过这个程序，你可以输入链表长度和元素，然后得到逆置后的结果。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

跳转到最佳答案楼层

FishC · 发表于 2024-10-18 17:24:35

要在C++中实现单链表逆置，且只利用原链表的存储空间，可以通过指针操作来改变链表的节点指向。以下是一个简单的实现：

#include <iostream>
struct Node {
int data;
Node* next;
Node(int val) : data(val), next(nullptr) {}
};
class LinkedList {
public:
Node* head;
LinkedList() : head(nullptr) {}
void append(int val) {
if (!head) {
head = new Node(val);
} else {
Node* temp = head;
while (temp->next) {
temp = temp->next;
}
temp->next = new Node(val);
}
}
void reverse() {
Node* prev = nullptr;
Node* current = head;
Node* next = nullptr;
while (current) {
next = current->next; // Save next
current->next = prev; // Reverse current node's pointer
prev = current; // Move pointers one position forward
current = next;
}
head = prev;
}
void print() const {
Node* temp = head;
while (temp) {
std::cout << temp->data;
if (temp->next) {
std::cout << " ";
}
temp = temp->next;
}
std::cout << "\n";
}
};
int main() {
int n;
std::cin >> n;
LinkedList list;
for (int i = 0; i < n; ++i) {
int val;
std::cin >> val;
list.append(val);
}
list.reverse();
list.print();
return 0;
}

复制代码

### 代码说明：
- **Node 结构体**：用于表示链表节点，包含数据和指针用于指向下一个节点。
- **LinkedList 类**：用于管理链表，包括添加新节点 (`append` 方法)、反转链表 (`reverse` 方法) 和打印链表 (`print` 方法) 的功能。
- **reverse 方法**：通过改变节点的指向来逆置链表，不需要额外的存储空间。
- **main 函数**：负责输入并调用上述功能进行链表处理。

通过这个程序，你可以输入链表长度和元素，然后得到逆置后的结果。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

账号		自动登录	找回密码
密码			立即注册