DFS 递归实战：链表反转与两两交换节点

DFS 递归实战：链表反转与两两交换节点

DFS（深度优先搜索）是处理树形结构和图结构问题的利器，尤其在链表递归操作中，理解遍历顺序至关重要。本文将结合两个经典案例，深入剖析递归在链表反转与节点交换中的应用。

1. 反转链表

题目链接： 206. 反转链表

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

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

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

思路分析

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

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

微观角度分析

从函数职责来看，子问题就是反转链表。

ListNode dfs(ListNode head)

我们只关心某一个子问题在做什么，即把当前节点及之后的部分反转。

宏观角度分析

明确 dfs 的含义：dfs 函数就是把链表反转并将新的头节点返回。 例如将 2 到 5 节点反转返回新的头节点，2~5 的新链表与 1 形成的链表再将 1 反转。

递归出口： 当链表只有一个节点或者当前节点为 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;
         newHead;
    }
}