[每日算法 - 阿里机试] leetcode19. 删除链表的倒数第 N 个结点

入口

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能，轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/remove-nth-node-from-end-of-list/description/

题目描述

给你一个链表，删除链表的倒数第 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

方法一：栈

• 链表顺序入栈
• 将链表后n个节点出栈
• 获取需要删除的第n个元素，变更next
• 返回虚拟节点dummy.next即可

图示

Java实例

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // 定义虚拟节点
        ListNode dummy = new ListNode(0, head);
        Deque stack = new LinkedList();
        
        // 防止需要删除节点为头节点时的空指针异常，将虚拟节点推入栈中
        stack.push(dummy);
        
        // 将链表中的每个节点推入栈中
        while (head != null) {
            stack.push(head);
            head = head.next;
        }
        
        // 弹出栈中的前n个节点，使栈顶元素为倒数第n个节点的前一个节点
        for (int i = 0; i < n; i++) {
            stack.pop();
        }
        
        // 获取倒数第n个节点的前一个节点
        ListNode pre = stack.peek();
        
        // 将前一个节点的next指针跳过倒数第n个节点，直接指向倒数第n个节点的下一个节点
        pre.next = pre.next.next;
        
        // 返回虚拟节点的下一个节点作为新链表的头节点
        return dummy.next;
    }
}

复杂度分析

• 时间复杂度：O(L)， L 是链表的长度。

• 空间复杂度：O(L)， L 是链表的长度，主要为栈的开销。

方法二：双指针

        使用快慢指针的方式，快指针与慢指针相差n-1，即快指针比慢指针超前了 n 个节点。 两个指针同时遍历链表，当快指针指向null时，此时慢指针正好指向倒数第n个元素的前一个元素。

Java示例

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // 定义虚拟节点
        ListNode dummy = new ListNode(0, head);
        ListNode first = head;
        ListNode second = dummy;
 
        // 将第一个指针向前移动 n 步
        for (int i = 0; i < n; i++) {
            first = first.next;
        }
 
        // 同时移动第一个和第二个指针，直到第一个指针为空
        while (first != null) {
            first = first.next;
            second = second.next;
        }
 
        // 此时第一个指针到达链表尾，second 正好指向倒数第 n 个元素的前一个节点
 
        // 将前一个节点的 next 指针跳过倒数第 n 个节点，直接指向倒数第 n 个节点的下一个节点
        second.next = second.next.next;
 
        // 返回虚拟节点的下一个节点作为新链表的头节点
        return dummy.next;
    }
}

复杂度分析

• 时间复杂度：O(L)，L 是链表的长度。

• 空间复杂度：O(1)。