链表的递归思想

在数据结构和算法中，递归是一种非常抽象的知识点，理解的难度和动态规划同属一个等级，我们的很多的数据结构和算法的编码都要用到递归，比如DFS深度优先搜索、前中后序二叉树遍历等等。
理解递归，就要将递归这两个字拆分开来，数据去过的过程叫“递”，回来的过程叫“归”，这里可以举一个比较极端的例子：

当你在电影院找自己是第几排，但是电影院太黑，看不清自己是第几排，于是你就问前一排的人他是第几排，他的排数+1，就是你的排数；但是这位同志也不清楚自己是第几排，于是就问了他前一排的人；就这样一步一步的向前问，终于是问到了第一排，于是数据开始往回走，第二排知道是第二排，第三排知道自己是第三排，最后你知道了你是哪一排

那么在上文的问题中，我们可以得到一个很简单的递推公式

f(n) = f(n-1) + 1; 其中，f(1)=1，代表第一排的人知道自己是第一排

可以看到到了这一步就已经开始抽象了，所以这里有个很重要的理念

重要思想

递归和平铺直叙的思维方式完全相冲突，如果看到递归，就想在脑子里层层循环，层层带入，然后再层层返回，试图理解计算机每一步都是怎么执行的，这样很容易被绕进去；

对于递归代码，这种试图想清楚整个递和归过程的做法，实际上是进入了一个思维误区。很多时候，我们理解起来比较吃力，主要原因就是自己给自己制造了这种理解障碍。那正确的思维方式应该是怎样的呢？

如果一个问题 A 可以分解为若干子问题 B、C、D，你可以假设子问题 B、C、D 已经解决，在此基础上思考如何解决问题 A。而且，你只需要思考问题 A 与子问题 B、C、D 两层之间的关系即可，不需要一层一层往下思考子问题与子子问题，子子问题与子子子问题之间的关系。屏蔽掉递归细节，这样子理解起来就简单多了。

即编写递归代码的关键是，只要遇到递归，我们就把它抽象成一个递推公式，不用想一层层的调用关系，不要试图用人脑去分解递归的每个步骤。

在想要用到递归的时候，只要想好了他每一步要干什么，就大胆去验证，不需要完全明白他发生了什么，如果一定要搞明白，那就不要用递归的写法

那我们就来看一道例题，LeetCode-24-两两交换链表中的节点

看到题目想到了什么，两两交换，也就是重复两个一交换的过程，直到进行到链表尾，这个两个一交换的过程就是一个递推。

那我们可以采用这种方法

1. 使用一个head，将第一次两两交换之后的节点保存下来，这个节点就是全部转换完之后的链表头
2. 使用一个prev指针，指向当前节点的上一个节点；使用一个curr节点，指向当前节点；使用一个next节点，指向当前节点的下一个节点 ```java //这里说的是两两交换，所以可以理解为两个一组，反转这组链表 //写成代码就是这段代码

int k = 2; //意思是两个一组

//prev = null //next = null while(curr != null && k>0){ next = curr.next; //1 curr.next = prev; //2 prev = curr; //3 curr = next; //4 k—; }

//我们首先确定了哪个是当前节点，第1步指定了next节点是什么 //第二步让当前节点的next指向自己的上一个节点 //第3步和第4步的意思是让当前节点和下个节点向后推进，k—指的是这组链表已经处理了一个元素

![](https://cdn.nlark.com/yuque/0/2022/gif/25444226/1642056131304-50a0b841-4ca6-4f1b-852a-eb173509531b.gif#clientId=u83bbcfa4-74d9-4&crop=0&crop=0&crop=1&crop=1&from=paste&id=uff5d73b4&margin=%5Bobject%20Object%5D&originHeight=700&originWidth=1920&originalType=url&ratio=1&rotation=0&showTitle=false&status=done&style=none&taskId=u1aea3d9c-b793-4aee-b501-48a56e192aa&title=)
如果我们把这个当成整个算法的第一步操作，当完成了这一组的操作后，我们发现，整个链表的头，是现在的prev，而我们传入的原本的列表头，变成了最后一个节点，那么我们就把这最后一个节点，继续指向curr，就能完成一组一组的反转，而第一步操作后的prev，就是整个列表的返回值；
3. 进行边界检测，确定上文链表无节点、单节点、双节点和不符合k个一组的情况
那么我们最终的代码就是这个样子
```java
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {
        int k = 2;
        ListNode next = null;
        ListNode prev = null;
        ListNode curr = head;
        int j = k;
        ListNode test = head;
        while(test != null && j>0){
            test = test.next;
            j--;
        }
        if(test == null && j != 0){
            return head;
        }
        while(curr != null && k>0){
            next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
            k--;
        }
        if(curr == null && k != 0){
            return head;
        }
        head.next = swapPairs(curr);
        return prev;
    }
}