一、链表的基础知识、递归方法的基本思路链表基础链表是一种非连续的线性存储结构核心单元是节点 ListNode 。每个节点包含两部分val 存储当前节点的值next 指向下一个节点的引用指针单链表特点内存不连续不像数组下标直接访问查询效率低需要从头遍历插入、删除效率高不需要整体移动元素最后一个节点的 next null 代表链表结束。Java 节点基础定义javaclass ListNode {int val;ListNode next;ListNode() {}ListNode(int val) { this.val val; }ListNode(int val, ListNode next) {this.val val;this.next next;}}递归基本思路递归本质函数自己调用自己两大必备要素终止条件基线条件什么时候停止递归防止死循环栈溢出递推公式子问题把大问题拆成更小的相同子问题先解决后面一部分链表再处理当前节点。链表递归通用思想先处理后面的子链表回溯的时候修改节点指向。二、反转链表 LeetCode 206题目描述给你单链表的头节点 head 请你反转链表并返回反转后的头结点。示例 1 → 2 → 3 → null 反转后 3 → 2 → 1 → null递归解题思路基线条件如果 head null 或者 head.next null 直接返回 head单个节点不用反转递归反转后面的子链表 newHead reverseList(head.next)回溯阶段反转指向 head.next.next head 让后一个节点反过来指向自己当前节点断开原来的指向 head.next null返回新的链表头节点 newHeadJava完整代码javaclass Solution {public ListNode reverseList(ListNode head) {// 递归终止条件if(head null || head.next null){return head;}// 递归反转后面链表ListNode newHead reverseList(head.next);// 反转节点指向head.next.next head;head.next null;return newHead;}}过程理解递归一路走到最后一个节点从尾部开始一点点调转箭头从后往前完成整条链表反转。三、两两交换链表中的节点 LeetCode 24题目描述给链表两两交换其中相邻的节点并返回交换后的链表。不能单纯改变节点内部的值必须实际交换节点本身。示例 1→2→3→4 输出 2→1→4→3递归解题思路基线条件 head null 或者 head.next null 直接返回没有两个节点可以交换定义第二个节点 nextNode head.next递归处理后面一组节点把交换完成后的结果交给 head.next交换两个节点 nextNode.next head返回交换完成后的新头结点 nextNodeJava完整代码javaclass Solution {public ListNode swapPairs(ListNode head) {// 递归终止条件没有节点 / 只剩单个节点if(head null || head.next null){return head;}ListNode nextNode head.next;// 递归处理后面的链表连接到当前head后面head.next swapPairs(nextNode.next);// 交换两个节点nextNode.next head;return nextNode;}}思路总结每次只交换前两个节点剩下的链表交给递归函数处理回溯自动拼接好整条链表。四、学习小结链表适合用递归优先解决后半段子链表回溯修改指针反转链表从尾部反向修改next指向两两交换每一组两个节点互换递归处理后续分组。