【DFS】天子呼来不上船,自称臣是酒中仙 - 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即可.

三. 代码实现

class Solution {
    public ListNode reverseList(ListNode head) {
        return dfs(head);
    }
    public ListNode dfs(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就不用交换,直接返回头节点.

二. 代码实现

class Solution {
    public ListNode swapPairs(ListNode head) {
        return dfs(head);
    }
    public ListNode dfs(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;
    }
}

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

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

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