C/C++教程

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++采用递归的方式实现链表反转的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!