数据结构与算法-03链表-04

链表与递归

在链表操作中移除、反转经常会用到递归实现。通过力扣案例理解链表常规操作中的递归实现。

移除数据

删除链表的节点

问题

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;
}