2024年4月30日发(作者：)

编写算法：实现带头结点单链表的逆置算法

引言

单链表是一种常见的数据结构，它由一系列节点组成，每个节点包含两部分：数据

域和指针域。其中，数据域用于存储数据，指针域用于指向下一个节点。在单链表

中，头结点是第一个节点之前的一个特殊节点，它不存储任何数据。

逆置（或反转）单链表是将原始链表中的节点顺序颠倒过来。例如，给定一个单链

表：1 -> 2 -> 3 -> 4 -> nullptr，逆置后的结果为：4 -> 3 -> 2 -> 1 ->

nullptr。

本文将介绍如何实现带头结点单链表的逆置算法，并给出相应的C++代码实现。

算法思路

要实现带头结点单链表的逆置算法，可以使用迭代或递归两种方法。

迭代方法

迭代方法通过遍历原始链表中的每个节点，并修改其指针域来实现逆置。具体步骤

如下：

1. 如果链表为空或只有一个节点，则直接返回。

2. 定义三个指针：prev、curr和next。

– prev指向当前节点的前一个节点（初始时为nullptr）；

– curr指向当前节点；

– next指向当前节点的下一个节点。

3. 进行循环，直到curr指向nullptr为止：

– 将curr的指针域修改为prev；

– 将prev指向curr；

– 将curr指向next；

– 将next指向下一个节点。

4. 修改头结点的指针域为nullptr，将prev作为新的头结点。

递归方法

递归方法通过逐层调用函数来实现逆置。具体步骤如下：

1. 如果链表为空或只有一个节点，则直接返回。

2. 定义一个递归函数

reverseList

，该函数接收一个参数：当前节点

head

。

3. 递归终止条件：如果当前节点或当前节点的下一个节点为空，则返回当前节

点。

4. 在递归调用前，先逆置从下一个节点开始的子链表，并将返回结果保存在变

量

newHead

中。

5. 将当前节点的下一个节点的指针域修改为当前节点（即将子链表的尾部连接

到当前节点）。

6. 将当前节点的指针域修改为空（即将当前节点作为新链表的尾部）。

7. 返回

newHead

作为新链表的头结点。

C++代码实现

#include

struct ListNode {

int val;

ListNode* next;

ListNode(int x) : val(x), next(nullptr) {}

};

ListNode* reverseList(ListNode* head) {

if (head == nullptr || head->next == nullptr) {

return head;

}

ListNode* prev = nullptr;

ListNode* curr = head;

ListNode* next = nullptr;

while (curr != nullptr) {

next = curr->next;

curr->next = prev;

prev = curr;

curr = next;

}

return prev;

}

ListNode* reverseListRecursive(ListNode* head) {

if (head == nullptr || head->next == nullptr) {

return head;

}

ListNode* newHead = reverseListRecursive(head->next);

head->next->next = head;

head->next = nullptr;

return newHead;

}

int main() {

// 创建链表：1 -> 2 -> 3 -> 4 -> nullptr

ListNode* head = new ListNode(0);

// 头结点

ListNode* node1 = new ListNode(1);

ListNode* node2 = new ListNode(2);

ListNode* node3 = new ListNode(3);

head->next = node1;

node1->next = node2;

node2->next = node3;

// 迭代方法逆置链表

head = reverseList(head);

// 输出逆置后的链表：4 -> 3 -> 2 -> 1 -> nullptr

ListNode* tempNode = head;

while (tempNode != nullptr) {

std::cout << tempNode->val << " ";

tempNode= tempNode->next;

}

std::cout << std::endl;

// 递归方法逆置链表

head= reverseListRecursive(head);

// 输出逆置后的链表：1 -> 2 -> 3 -> 4 -> nullptr

tempNode = head;

while (tempNode != nullptr) {

std::cout << tempNode->val << " ";

tempNode= tempNode->next;

}

return 0;

}

总结

本文介绍了如何实现带头结点单链表的逆置算法。通过迭代方法或递归方法，可以

将原始链表中的节点顺序颠倒过来。迭代方法通过循环遍历链表中的每个节点，并

修改其指针域来实现逆置；递归方法则通过逐层调用函数来实现逆置。

在C++代码实现中，我们使用了两个函数

reverseList

和

reverseListRecursive

分别

对应迭代方法和递归方法。我们还创建了一个带头结点的单链表，并对其进行了逆

置操作，并输出结果。

希望本文对你理解带头结点单链表的逆置算法有所帮助！