用递归方法逆置带头节点的单链表 用c++
时间: 2024-11-30 13:20:12 浏览: 5
递归、非递归的方法实现单向链表的逆置操作
在C++中,你可以使用递归的方法来逆置一个带头节点的单链表。递归的关键在于将复杂的问题分解成更小的子问题,并且每次解决完子问题后将结果链接起来。这里是一个基本的思路:
```cpp
// 假设头节点为ListNode,包含数据域data和指向下一个节点的指针next
struct ListNode {
int data;
ListNode* next;
};
ListNode* reverseList(ListNode* head) {
// 如果链表为空或者只有一个元素,无需反转,直接返回头节点
if (!head || !head->next) {
return head;
}
// 递归步骤:创建一个新的头节点,它将成为原链表第一个节点的前驱
ListNode* newHead = new ListNode(head->data);
// 递归处理剩余部分,并连接新的头节点和当前链表的头节点
newHead->next = reverseList(head->next);
// 最终返回新链表的头节点
return newHead;
}
```
这个函数会返回一个新的链表,其节点顺序是原始链表的反向。
阅读全文