#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; }给出以上代码框架，按数字输入顺序创建单链表。不可借助数组、容器，不可开辟新结点空间。编写函数，在原链表上实现单链表的反转。例如单链表10->20->30，反转后变为单链表30->20->10。 注：不符合题目要求，使用上述逆序输出不计分。 输入 测试次数t 每组测试数据一行，格式如下： 数据个数n，后跟n个整数 输出 对每组测试数据，输出反转前后的单链表。 输入样例1 2\n 10 1 2 3 4 5 6 7 8 9 10\n 4 19 20 15 -10 输出样例1 1 2 3 4 5 6 7 8 9 10 \n 10 9 8 7 6 5 4 3 2 1 \n 19 20 15 -10 \n -10 15 20 19

以下是完整的代码实现以及解释： ### 完整代码 ```cpp #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; cin >> n; if (n == 0) { head = nullptr; return; } cin >> head->data; head->next = nullptr; tail = head; for (i = 1; i < n; ++i) { p = new Node; cin >> p->data; p->next = nullptr; tail->next = p; tail = p; } } void display(struct Node *head) { // 输出单链表 struct Node *p = head; while (p != nullptr) { cout << p->data << " "; p = p->next; } cout << endl; } void deletelist(struct Node *&head) { // 删除单链表 struct Node *p; while (head != nullptr) { p = head; head = head->next; delete p; } } // 实现原地反转链表的功能 void reverselist(struct Node *&head) { struct Node *prev = nullptr; // 当前节点的前驱 struct Node *curr = head; // 当前正在处理的节点 struct Node *next_node = nullptr; // 下一个节点 while (curr != nullptr) { next_node = curr->next; // 先保存下一个节点的位置 curr->next = prev; // 修改当前节点的指针方向，使其指向它的前驱节点 prev = curr; // 更新 prev 和 curr 移动到下一位置 curr = next_node; } head = prev; // 最终将 head 设置为最后一个非空节点（原始尾节点） } int main() { int t; cin >> t; while (t--) { struct Node *head = new Node(); createlist_r(head); display(head); // 显示原始列表 reverselist(head); // 反转列表 display(head); // 显示反转后的列表 deletelist(head); // 清理内存释放资源 } return 0; } ``` --- ### 详细说明 #### **核心思路** 该程序的核心任务是在不额外分配新节点的情况下，完成单向链表的就地翻转。这就意味着我们只需要调整原有节点之间的链接关系即可。 #### **关键步骤解析** 1. **`createlist_r()` 构造链表**： - 功能：从键盘输入构造一条包含指定数量元素的单向链表。 - 特别注意的是，在构建过程中每个新插入的节点都作为链表末端的新成员附加上去。 2. **`display()` 打印链表**： - 遍历整个链表并将每一个节点的数据域打印出来直到遇到结束标志（NULL）为止。 3. **`reverselist()` 原地翻转链表**： - 初始化三个辅助指针：previous (`prev`)、current(`curr`)和temp存储临时后继(temporary next node pointer). - 循环遍历原链表所有节点: - 记录下一次迭代需要移