【DFS】天子呼来不上船,自称臣是酒中仙 - 2.递归

本篇博客给大家带来的是DFS深度优先遍历的解法技巧,在后面的文章中题目会涉及到回溯和剪枝,遇到了一并讲清楚.
🐎文章专栏: DFS
🚀若有问题 评论区见
❤ 欢迎大家点赞 评论 收藏 分享
如果你不知道分享给谁,那就分享给薯条.
你们的支持是我不断创作的动力 .

王子,公主请阅🚀

• 要开心
  • 要快乐
    • 顺便进步
• 1. 反转链表
• 2. 两两交换链表中的节点

要开心

要快乐

顺便进步

1. 反转链表

题目链接:206. 反转链表

题目内容:
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 3：

输入：head = []
输出：[]

提示：

链表中节点的数目范围是 [0, 5000]
-5000 <= Node.val <= 5000

题目链接:link

题目内容:

一. 分析

如果按前序遍历的顺序递归能不能解决这道题?
答案是解决不了.

如上图, 当我修改完节点2的时候,需要往下一个节点修改,但此时2的next节点变成两个了,分别是节点1和节点3,这个时候就会出问题,所以舍弃前序遍历改用后序遍历.

二. 后序遍历递归的具体步骤

第一种分析方式 微观角度(dfs函数在做什么)来分析
1. 重复子问题(函数头)
子问题就是反转链表, ListNode dfs(ListNode head)

2. 只关心某一个子问题在做什么

第二种分析方式 宏观角度来分析
1. 明确dfs的含义
dfs函数就是把链表反转并将新的头节点返回

如上图例子中,从宏观角度看就是将2节点到5节点反转返回新的头节点,2~5的新链表与1形成的链表再将1反转.
2. 怎么将1反转?(函数体)

3. 递归出口
当链表只有一个节点或者当前节点为null时,无需反转直接return head即可.

三. 代码实现

classSolution{publicListNodereverseList(ListNode head){returndfs(head);}publicListNodedfs(ListNode head){if(head ==null|| head.next ==null){return head;}ListNode newHead =dfs(head.next); head.next.next = head; head.next =null;return newHead;}}

2. 两两交换链表中的节点

题目链接:24. 两两交换链表中的节点

题目内容:
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

提示：

链表中节点的数目在范围 [0, 100] 内
0 <= Node.val <= 100

一. 宏观角度分析

1. 明确dfs的含义
两两交换节点并返回新的头节点.

如上图例子,除第一第二个节点,其余节点两两交换,返回新的头节点tmp, 只有一个节点或者节点为null就不用交换.

2. 第一第二个节点如何交换?

3. 递归出口
只有一个节点或者节点为null就不用交换,直接返回头节点.

二. 代码实现

classSolution{publicListNodeswapPairs(ListNode head){returndfs(head);}publicListNodedfs(ListNode head){if(head ==null|| head.next ==null){return head;}ListNode tmp =dfs(head.next.next);ListNode ret = head.next; head.next.next = head; head.next = tmp;return ret;}}

总结: 宏观角度总给人代码会出错的不自信, 但是分析起来是非常方便,快捷的. 能用则用,实在不行,再从微观角度慢慢分析.

本篇博客到这里就结束啦, 感谢观看 ❤❤❤

🐎期待与你的下一次相遇😊😊😊