链表与递归
在链表操作中移除、反转经常会用到递归实现。通过力扣案例理解链表常规操作中的递归实现。
移除数据
删除链表的节点
问题
LCR 136. 删除链表的节点 - 力扣（LeetCode）
问题描述
给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。
返回删除后的链表的头节点。
示例 1:
输入: head = [4,5,1,9], val = 5
输出: [4,1,9]
解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.
示例 2:
输入: head = [4,5,1,9], val = 1
输出: [4,5,9]
解释: 给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.
解决方案
参考实现
移除链表元素
问题
[力扣203] 203. 移除链表元素 - 力扣（LeetCode）
问题描述
给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
示例 1：
输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]
示例 2：
输入：head = [], val = 1
输出：[]
示例 3：
输入：head = [7,7,7,7], val = 7
输出：[]
解决方案
使用递归删除
参考实现
class Solution {public ListNode removeElements(ListNode curr, int val) {//递归终止条件if(curr ==null) return null;ListNode node = removeElements(curr.next, val);if(curr.val == val){return node;}else{curr.next = node;return curr;}}
}
从链表中移除节点
问题
[力扣2487] 2487. 从链表中移除节点 - 力扣（LeetCode）
题目描述
给你一个链表的头节点
head。移除每个右侧有一个更大数值的节点。返回修改后链表的头节点head。示例 1：
输入：head = [5,2,13,3,8] 输出：[13,8] 解释：需要移除的节点是 5 ，2 和 3 。 - 节点 13 在节点 5 右侧。 - 节点 13 在节点 2 右侧。 - 节点 8 在节点 3 右侧。示例 2：
输入：head = [1,1,1,1] 输出：[1,1,1,1] 解释：每个节点的值都是 1 ，所以没有需要移除的节点。
解决方案
参考实现
class Solution {public ListNode removeNodes(ListNode curr) {if (curr == null)return null;ListNode node = removeNodes(curr.next);if (curr.next != null && curr.val < node.val) {return node;} else {curr.next = node;return curr;}}
}
删除链表中中重复元素
问题
[力扣83] 83. 删除排序链表中的重复元素 - 力扣（LeetCode）
问题描述
给定一个已排序的链表的头
head， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。
示例 1：
输入：head = [1,1,2]
输出：[1,2]
示例 2：
输入：head = [1,1,2,3,3]
输出：[1,2,3]
解决方案
类似从链表中删除某个节点的方式(递归方式)
参考实现
class Solution {public ListNode deleteDuplicates(ListNode head) {if(head == null) return null;ListNode node = deleteDuplicates(head.next);if(head.next!=null && head.val == node.val){return node;}else{head.next = node;return head;}}
}
链表的反转
算法核心
递归寻找最后一个节点的前一个节点。
链表的反转涉及到三个节点的交互。
实现流程
参考实现
public Node reverse2(Node head) {if (head.next == null) return head;Node curr = reverse2(head.next);head.next.next = head;head.next = null;return curr;
}
测试一下
92. 反转链表 II - 力扣（LeetCode）
