按数字输入顺序创建单链表。不可借助数组、容器，不可开辟新结点空间。编写函数，在原链表上实现单链表的反转。例如单链表10->20->30，反转后变为单链表30->20->10。#include <iostream> using namespace std; struct Node { int data; struct Node *next; }; //链表结点结构 void createlist_r(struct Node *&head)//尾插法建单链表，没有头结点，输入顺序就是结点顺序 { int n,i; struct Node *p,*tail; head=new Node; cin>>n; cin>>head->data; head->next=nullptr; tail=head; for(i=0; i<n-1; i++) { p=new Node; cin>>p->data; p->next=nullptr; tail->next=p; tail=p; } } void display(struct Node *head)//输出不带头结点的单链表 { struct Node *p; p=head; while(p!=nullptr) { cout<<p->data<<" "; p=p->next; } cout<<endl; } void deletelist(struct Node *&head) //删除单链表 { struct Node *p; while(head) { p=head; head=head->next; delete(p); } head=nullptr; //一定要赋值为空，否则容易造成野指针访问 } //请在以下空白处编写reverselit函数，完成原地逆转，即过程中不在分配新的结点也不撤销旧的结点 /********** Write your code here! **********/ /*******************************************/ int main() { int t; cin>>t; while(t--) { struct Node *head; createlist_r(head); display(head); reverselist(head); display(head); deletelist(head); } return 0; }

### C++ 单链表原地反转函数实现 在不借助数组、容器以及不开辟新节点空间的情况下，可以利用三个指针变量 `prev`、`current` 和 `nextNode` 来完成单链表的原地反转操作。以下是详细的实现方法： #### 函数定义 通过迭代的方式遍历整个链表，并逐步调整每个节点的 `next` 指针方向。 ```cpp struct ListNode { int data; ListNode* next; }; ListNode* reverseList(ListNode* head) { ListNode* prev = nullptr; // 初始化前驱节点为空 ListNode* current = head; // 当前节点从头节点开始 while (current != nullptr) { // 遍历直到当前节点为空 ListNode* nextNode = current->next; // 保存下一个节点 current->next = prev; // 将当前节点的 next 指向前驱节点 prev = current; // 更新前驱节点为当前节点 current = nextNode; // 移动到下一个节点 } return prev; // 返回新的头节点（即原来的尾节点） } ``` 上述代码实现了单链表的原地反转功能[^1]。其中，`prev` 初始值设为 `nullptr` 表示反转后的新链表尾部指向空；`current` 是正在处理的节点；`nextNode` 用于临时存储当前节点的下一节点地址，防止丢失链表结构。 #### 完整程序示例 下面提供了一个完整的 C++ 程序，展示如何构建单链表并调用反转函数： ```cpp #include <iostream> using namespace std; // 定义链表节点结构体 struct ListNode { int data; ListNode* next; ListNode(int val) : data(val), next(nullptr) {} }; // 插入数据到链表中 void insertAtEnd(ListNode*& head, int value) { ListNode* newNode = new ListNode(value); if (!head) { head = newNode; } else { ListNode* temp = head; while (temp->next) { temp = temp->next; } temp->next = newNode; } } // 打印链表 void printList(ListNode* node) { while (node) { cout << node->data << "->"; node = node->next; } cout << "NULL" << endl; } // 反转链表的核心逻辑 ListNode* reverseList(ListNode* head) { ListNode* prev = nullptr; ListNode* current = head; while (current != nullptr) { ListNode* nextNode = current->next; current->next = prev; prev = current; current = nextNode; } return prev; } int main() { ListNode* head = nullptr; // 构建链表：10 -> 20 -> 30 insertAtEnd(head, 10); insertAtEnd(head, 20); insertAtEnd(head, 30); cout << "Original List: "; printList(head); // 调用反转函数 head = reverseList(head); cout << "Reversed List: "; printList(head); return 0; } ``` 此程序展示了如何创建一个简单的单链表，并使用前面提到的 `reverseList` 函数将其反转[^2]。 #### 关键点解析 - **时间复杂度**：由于只需一次遍历即可完成反转操作，因此算法的时间复杂度为 O(n)，n 为链表长度。 - **空间复杂度**：仅使用了固定数量的额外指针变量 (`prev`, `current`, `nextNode`)，故空间复杂度为 O(1)[^4]。 ---