LeetCode | 19 | 删除链表的倒数第 N 个结点 | 双指针 | 递归 | 栈

这道题还可以用递归法，你想到了吗？

---

LeetCode链接：19. 删除链表的倒数第 N 个结点

---

1.题目描述

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

示例 1：

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

示例 2：

输入：head = [1], n = 1
输出：[]

示例 3：

输入：head = [1,2], n = 1
输出：[1]

提示：

• 链表中结点的数目为 sz
• 1 <= sz <= 30
• 0 <= Node.val <= 100
• 1 <= n <= sz

进阶：你能尝试使用一趟扫描实现吗？

2.题解

2.1 暴力解法

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // 获取链表的长度
        int length = getLength(head);

        // 判断要删除的节点位置
        int index = length - n;

        // 创建一个虚拟头节点，指向head
        ListNode dummy = new ListNode(0, head);

        // 要删除的结点的前一个结点
        ListNode pre = dummy;
        for (int i = 0; i < index; i++) {
            pre = pre.next;
        }

        // 执行删除操作
        pre.next = pre.next.next;

        // 返回新链表的头节点
        return dummy.next;
    }

    // 获取链表长度函数
    public int getLength(ListNode head) {
        int length = 0;
        while (head != null) {
            length++;
            head = head.next;
        }
        return length;
    }
}

2.2 双指针- 暴力解法优化

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // 创建一个虚拟头节点，指向head
        ListNode dummy = new ListNode(0, head);
        
        // 初始化双指针，都指向虚拟头节点
        ListNode first = dummy, second = dummy;
        
        // 让first指针先走n步
        for (int i = 0; i < n; i++) {
            first = first.next;
        }
        
        // 同时移动first和second指针，直到first指针到达链表末尾
        while (first.next != null) {
            first = first.next;
            second = second.next;
        }
        
        // 此时second指针的下一个节点就是要删除的节点
        // 执行删除操作
        second.next = second.next.next;
        
        // 返回新链表的头节点
        return dummy.next;
    }
}

2.3 递归

class Solution {
    int count = 0; // 计数器，用于记录递归层数

    // 递归法 三步走
    // 1.确定形参和返回值
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // 2.确定单层递归条件
        if (head == null) return null;

        // 3.确定单层递归逻辑
        head.next = removeNthFromEnd(head.next, n); // 递归到链表末尾
        count++; // 递归返回时增加计数
        return count == n ? head.next : head; // 如果当前节点是倒数第n个节点，跳过它
    }
}

2.4 借助栈

• 我们知道递归的本质就是栈，因此我们也可以使用栈来解决这道题目

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        //虚设一个头节点  
        ListNode newHead = new ListNode(0,head);
        //创建栈用于存储链表结点
        Stack<ListNode> stack = new Stack<>();
        //开始迭代，所有结点入栈
        ListNode cur = newHead;
        while(cur != null){
            stack.push(cur);
            cur = cur.next;
        }

        //从栈顶开始弹出元素，一直弹到要删除的位置
        for(int i=0;i<n;i++){
            stack.pop();
        }
        //再弹出的元素就是要删除的结点的前一个元素
        ListNode pre = stack.pop();
        //删除操作
        pre.next = pre.next.next;
        //返回结果
        return newHead.next;
    }
}