C++采用递归的方式实现链表反转

本文主要是介绍C++采用递归的方式实现链表反转，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

考虑使用递归法遍历链表，当越过尾节点后终止递归，在回溯时修改各节点的 next 引用指向。

reverse(pre, cur) 递归函数：

　　终止条件：当 cur 为空，则返回尾节点 pre （即反转链表的头节点）；

　　递归后继节点，记录返回值（即反转链表的头节点）为 res ；

　　修改当前节点 cur 引用指向前驱节点 pre ；

　　返回反转链表的头节点 res。

reverseList(head) 函数：

　　调用并返回 reverse(nullptr, head) 。传入 nullptr是因为反转链表后， head 节点指向 nullptr。

复杂度分析：

　　时间复杂度 O(N) ： 遍历链表使用线性大小时间。

　　空间复杂度 O(N)： 遍历链表的递归深度达到 N ，系统使用 O(N) 大小额外空间。

ListNode* reverse(ListNode* pre, ListNode* cur) {
    if(cur == nullptr) return pre;
    ListNode* temp = cur->next;
    cur->next = pre;
    pre = cur;
    cur = temp;
    return reverse(pre, cur);
}

ListNode* reverseList(ListNode* head) {
    return reverse(nullptr, head);
}

这篇关于C++采用递归的方式实现链表反转的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！