有一个整数单链表I,设计一个算法逆置L中的所有结点(实现算法时,请使用函数模板,在调用时初始化为整型单链表)。
时间: 2024-10-23 19:16:28 浏览: 28
为了逆置一个整数单链表,你可以采用迭代或递归的方式来实现。这里我们提供一种迭代的方法,通过设置两个指针 `prev` 和 `current`,分别指向当前节点的前一个节点和当前节点。然后每次迭代,将 `current` 的下一个节点赋值给 `current`,同时将 `current` 指向 `prev`,直到 `current` 为空,即遍历完整个链表。
```cpp
template <typename T>
struct ListNode {
T val;
ListNode *next;
ListNode(T x) : val(x), next(NULL) {}
};
template <typename T>
void reverseList(ListNode<T> **head) {
if (*head == nullptr || (*head)->next == nullptr) {
return; // 如果链表为空或只有一个元素,无需反转
}
ListNode<T> *prev = nullptr, *current = *head;
while (current != nullptr) {
ListNode<T> *temp = current->next; // 保存当前节点的下一个节点
current->next = prev; // 将当前节点的next指向前一个节点
prev = current; // 更新前一个节点
current = temp; // 更新当前节点
}
*head = prev; // 最后更新头节点为原链表的最后一个节点
}
// 使用示例:
ListNode<int> *list = createLinkedList(); // 创建一个整型链表
reverseList(&list); // 调用逆置函数
```
阅读全文