先建立线性表的带头结点单链表表示形式,之后在不借助辅助结点空间的情况下实现单链表的逆置,并将结果输出
时间: 2024-09-21 12:09:26 浏览: 39
JAVA单链表的简单操作(递增单链表插入数据,链表逆置,链表逆序合成)
在C++中,我们可以使用结构体或类来定义一个单链表节点,其中包含数据域(通常是整型或其他类型)以及指向下一个节点的指针。带头结点的单链表表示形式通常如下:
```cpp
// 定义链表节点
struct ListNode {
int data; // 数据域
ListNode* next; // 指向下一个节点的指针
};
```
接下来,我们可以通过遍历整个链表并在原地修改节点的next指针来实现单链表的逆置。这里的关键在于记住当前节点的前驱和后继节点。以下是一个简单的示例,展示了如何在不使用额外空间的情况下逆置链表:
```cpp
ListNode* reverseList(ListNode* head) {
if (head == nullptr || head->next == nullptr) {
return head;
}
ListNode* prev = nullptr, *current = head, *nextTemp = nullptr;
while (current != nullptr) {
nextTemp = current->next; // 保存当前节点的后继
current->next = prev; // 将当前节点的next指向前驱
prev = current; // 更新前驱为当前节点
current = nextTemp; // 移动到下一个节点
}
return prev; // 返回新的头节点,即原来的尾节点
}
```
要输出逆置后的链表,你可以编写一个遍历函数来打印节点的数据:
```cpp
void printList(ListNode* node) {
while (node != nullptr) {
cout << node->data << " ";
node = node->next;
}
cout << endl;
}
int main() {
// 初始化链表并逆置
ListNode* list = ... // 初始化链表
ListNode* reversedHead = reverseList(list);
// 输出逆置后的链表
printList(reversedHead);
return 0;
}
```
阅读全文