[已解决]单链表逆置

yangzhixiaohuli

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

原单链表如下所示：图片.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++中实现单链表逆置，且只利用原链表的存储空间，可以通过指针操作来改变链表的节点指向。以下是一个简单的实现：

1. #include <iostream>
   
2. 
   
3. struct Node {
   
4.     int data;
   
5.     Node* next;
   
6.     Node(int val) : data(val), next(nullptr) {}
   
7. };
   
8. 
   
9. class LinkedList {
   
10. public:
    
11.     Node* head;
    
12. 
    
13.     LinkedList() : head(nullptr) {}
    
14. 
    
15.     void append(int val) {
    
16.         if (!head) {
    
17.             head = new Node(val);
    
18.         } else {
    
19.             Node* temp = head;
    
20.             while (temp->next) {
    
21.                 temp = temp->next;
    
22.             }
    
23.             temp->next = new Node(val);
    
24.         }
    
25.     }
    
26. 
    
27.     void reverse() {
    
28.         Node* prev = nullptr;
    
29.         Node* current = head;
    
30.         Node* next = nullptr;
    
31.         
    
32.         while (current) {
    
33.             next = current->next;  // Save next
    
34.             current->next = prev;  // Reverse current node's pointer
    
35.             prev = current;        // Move pointers one position forward
    
36.             current = next;
    
37.         }
    
38.         head = prev;
    
39.     }
    
40. 
    
41.     void print() const {
    
42.         Node* temp = head;
    
43.         while (temp) {
    
44.             std::cout << temp->data;
    
45.             if (temp->next) {
    
46.                 std::cout << " ";
    
47.             }
    
48.             temp = temp->next;
    
49.         }
    
50.         std::cout << "\n";
    
51.     }
    
52. };
    
53. 
    
54. int main() {
    
55.     int n;
    
56.     std::cin >> n;
    
57.     LinkedList list;
    
58. 
    
59.     for (int i = 0; i < n; ++i) {
    
60.         int val;
    
61.         std::cin >> val;
    
62.         list.append(val);
    
63.     }
    
64. 
    
65.     list.reverse();
    
66.     list.print();
    
67. 
    
68.     return 0;
    
69. }

复制代码

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

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

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

跳转到最佳答案楼层

FishC

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

1. #include <iostream>
   
2. 
   
3. struct Node {
   
4.     int data;
   
5.     Node* next;
   
6.     Node(int val) : data(val), next(nullptr) {}
   
7. };
   
8. 
   
9. class LinkedList {
   
10. public:
    
11.     Node* head;
    
12. 
    
13.     LinkedList() : head(nullptr) {}
    
14. 
    
15.     void append(int val) {
    
16.         if (!head) {
    
17.             head = new Node(val);
    
18.         } else {
    
19.             Node* temp = head;
    
20.             while (temp->next) {
    
21.                 temp = temp->next;
    
22.             }
    
23.             temp->next = new Node(val);
    
24.         }
    
25.     }
    
26. 
    
27.     void reverse() {
    
28.         Node* prev = nullptr;
    
29.         Node* current = head;
    
30.         Node* next = nullptr;
    
31.         
    
32.         while (current) {
    
33.             next = current->next;  // Save next
    
34.             current->next = prev;  // Reverse current node's pointer
    
35.             prev = current;        // Move pointers one position forward
    
36.             current = next;
    
37.         }
    
38.         head = prev;
    
39.     }
    
40. 
    
41.     void print() const {
    
42.         Node* temp = head;
    
43.         while (temp) {
    
44.             std::cout << temp->data;
    
45.             if (temp->next) {
    
46.                 std::cout << " ";
    
47.             }
    
48.             temp = temp->next;
    
49.         }
    
50.         std::cout << "\n";
    
51.     }
    
52. };
    
53. 
    
54. int main() {
    
55.     int n;
    
56.     std::cin >> n;
    
57.     LinkedList list;
    
58. 
    
59.     for (int i = 0; i < n; ++i) {
    
60.         int val;
    
61.         std::cin >> val;
    
62.         list.append(val);
    
63.     }
    
64. 
    
65.     list.reverse();
    
66.     list.print();
    
67. 
    
68.     return 0;
    
69. }

复制代码

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

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

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