C++反转链表递归

简介: C++反转链表递归

C++反转链表递归

📟作者主页:慢热的陕西人

🌴专栏链接:力扣刷题日记

📣欢迎各位大佬👍点赞🔥关注🚓收藏,🍉留言


题目描述

LCR 024. 反转链表 - 力扣(LeetCode)

给定单链表的头节点 head ,请反转链表,并返回反转后的链表的头节点。

解题思路

这里我们采用递归的思路来解决首先我们分为两个视角来查看问题:

①宏观的视角

首先我们坚信reverseList(ListNode* head)这个函数可以帮我们逆置链表;

所以我们第一步reverseList(head->next);

head->next->next = head;

head->next = nullptr;

最后我们返回链表的头指针即可

②将链表看成一棵树的视角

简单说就是第一个视角的展开,我们先递归到最深层:

逆置操作:

继续:

最后:

总结:

如果我们把单链表看成一棵树我们仅需进行深度优先遍历即可。

代码

class Solution {
public:
    ListNode* reverseList(ListNode* head) 
    {
        if(head == nullptr)
        return head;
        if(head->next == nullptr)
        return head;
        ListNode* NewHead = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        return NewHead;
    }
};

复杂度分析

时间复杂度:

只遍历了一次相当于O(N);

空间复杂度:

没有额外使用O(1);

相关文章
|
6月前
|
C++
【链表】还不会用C++实现链表?一文教会你各种链表的实现
【链表】还不会用C++实现链表?一文教会你各种链表的实现
257 0
|
6月前
|
设计模式 中间件 程序员
【C/C++ 奇异递归模板模式 】C++中CRTP模式(Curiously Recurring Template Pattern)的艺术和科学
【C/C++ 奇异递归模板模式 】C++中CRTP模式(Curiously Recurring Template Pattern)的艺术和科学
310 3
|
5月前
|
算法 C++
算法笔记:递归(c++实现)
算法笔记:递归(c++实现)
|
6月前
|
算法
算法系列--递归(一)--与链表有关(上)
算法系列--递归(一)--与链表有关
64 0
|
4月前
|
存储 C++
C++的list-map链表与映射表
```markdown C++ 中的`list`和`map`提供链表和映射表功能。`list`是双向链表,支持头尾插入删除(`push_front/push_back/pop_front/pop_back`),迭代器遍历及任意位置插入删除。`map`是键值对集合,自动按键排序,支持直接通过键来添加、修改和删除元素。两者均能使用范围for循环遍历,`map`的`count`函数用于统计键值出现次数。 ```
|
5月前
|
存储 C++
C++的list-map链表与映射表
这篇教程介绍了C++中`list`链表和`map`映射表的基本使用。`list`链表可通过`push_front()`、`push_back()`、`pop_front()`和`pop_back()`进行元素的添加和删除,使用迭代器遍历并支持在任意位置插入或删除元素。`map`是一个键值对的集合,元素自动按键值排序,可使用下标操作符或`insert()`函数插入元素,通过迭代器遍历并修改键值对,同时提供`count()`方法统计键值出现次数。教程中包含多个示例代码以帮助理解和学习。
|
5月前
|
SQL 算法 数据可视化
LeetCode题目92:反转链表ll 【python 递归与迭代方法全解析】
LeetCode题目92:反转链表ll 【python 递归与迭代方法全解析】
|
6月前
|
算法 C++
c++算法学习笔记 (13) 链表
c++算法学习笔记 (13) 链表
|
5月前
|
C++ Python
UE C++ 链表
UE C++ 链表
|
5月前
|
C++ 容器
【C++进阶】深入STL之list:高效双向链表的使用技巧
【C++进阶】深入STL之list:高效双向链表的使用技巧
55 0