编程实现对一个单向链表的结点进行反转,也就是将链表结点按逆序排列,排序后链头将成为链尾,而链尾将成为链头。自定义函数名称及函数功能要求如下: (1)定义“createNode”函数,实现创建一个新结点。 (2)定义“createList”函数,实现一个单向链表的创建。 ● 在创建结点时通过键盘输入为每个结点的数据成员value进行赋值。 ● 使用“头插法”将每个结点逐一插入到链表中。 (3)定义“display”的函数,实现对链表所有结点的遍历输出。 (4)定义“reverse”的函数,实现对链表结点的反转
时间: 2023-12-10 21:37:17 浏览: 131
以下是实现上述功能的 C++ 代码:
```cpp
#include <iostream>
using namespace std;
// 定义链表结点结构体
struct ListNode {
int value;
ListNode* next;
};
// 创建一个新结点
ListNode* createNode(int value) {
ListNode* node = new ListNode;
node->value = value;
node->next = NULL;
return node;
}
// 创建链表
ListNode* createList() {
ListNode* head = NULL;
int value;
cout << "请输入结点的值,输入-1结束:" << endl;
cin >> value;
while (value != -1) {
ListNode* node = createNode(value);
node->next = head;
head = node;
cin >> value;
}
return head;
}
// 遍历链表并输出
void display(ListNode* head) {
cout << "链表结点的值为:" << endl;
while (head) {
cout << head->value << " ";
head = head->next;
}
cout << endl;
}
// 反转链表
ListNode* reverse(ListNode* head) {
ListNode* prev = NULL;
ListNode* curr = head;
while (curr) {
ListNode* temp = curr->next;
curr->next = prev;
prev = curr;
curr = temp;
}
return prev;
}
int main() {
ListNode* head = createList();
display(head);
head = reverse(head);
display(head);
return 0;
}
```
首先定义了链表结点的结构体 `ListNode`,包含一个整型数据成员和一个指向下一个结点的指针。然后定义了 `createNode` 函数,用于创建一个新的结点,并返回其指针。接着定义了 `createList` 函数,用于通过键盘输入创建一个单向链表,并使用头插法将每个结点逐一插入到链表中。
`display` 函数用于遍历链表并输出所有结点的值,方便我们查看链表的创建情况。`reverse` 函数用于反转链表,具体实现是使用两个指针 `prev` 和 `curr`,分别指向当前结点的前一个结点和当前结点,然后依次遍历链表,将 `curr->next` 指向 `prev`,同时向后移动 `prev` 和 `curr` 指针,最终返回反转后的链表头结点的指针。
在 `main` 函数中,我们先调用 `createList` 函数创建一个单向链表,然后调用 `display` 函数输出链表的结点值。接着将链表传入 `reverse` 函数进行反转,再次调用 `display` 函数输出反转后链表的结点值,从而完成链表结点反转的功能。
阅读全文