Java如何删除链表的倒数第N个节点

在Java中，链表是一种常见的数据结构，它由一系列节点组成，每个节点包含数据和指向下一个节点的指针。删除链表的倒数第N个节点是一个常见的操作，本文将详细介绍如何在Java中实现这一操作。

1. 问题描述

给定一个链表，删除链表的倒数第N个节点，并返回链表的头节点。例如，给定链表 1->2->3->4->5 和 N = 2，删除倒数第二个节点后，链表变为 1->2->3->5。

2. 解决思路

要删除链表的倒数第N个节点，我们可以使用双指针技巧。具体步骤如下：

1. 初始化两个指针：fast 和 slow，初始时都指向链表的头节点。
2. 移动 fast 指针：将 fast 指针向前移动 N 步，使得 fast 和 slow 之间相隔 N 个节点。
3. 同时移动 fast 和 slow 指针：当 fast 指针到达链表末尾时，slow 指针正好指向倒数第 N+1 个节点。
4. 删除倒数第N个节点：将 slow 指针的 next 指向 slow.next.next，从而跳过倒数第N个节点。

3. 代码实现

以下是Java代码的实现：

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

public class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // 创建一个虚拟头节点，简化边界条件处理
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        
        ListNode fast = dummy;
        ListNode slow = dummy;
        
        // 移动fast指针，使其与slow指针相隔n个节点
        for (int i = 0; i <= n; i++) {
            fast = fast.next;
        }
        
        // 同时移动fast和slow指针，直到fast到达链表末尾
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        
        // 删除倒数第n个节点
        slow.next = slow.next.next;
        
        // 返回链表的头节点
        return dummy.next;
    }
}

4. 代码解析

• 虚拟头节点：我们创建了一个虚拟头节点 dummy，并将其 next 指向链表的头节点。这样可以简化边界条件的处理，例如当需要删除的节点是头节点时。
• 双指针移动：fast 指针先移动 n+1 步，然后 fast 和 slow 指针同时移动，直到 fast 指针到达链表末尾。此时，slow 指针指向倒数第 n+1 个节点。
• 删除节点：通过将 slow.next 指向 slow.next.next，我们跳过了倒数第 n 个节点，实现了删除操作。

5. 复杂度分析

• 时间复杂度：O(L)，其中 L 是链表的长度。我们只需要遍历链表一次。
• 空间复杂度：O(1)，我们只使用了常数级别的额外空间。

6. 总结

通过使用双指针技巧，我们可以高效地删除链表的倒数第N个节点。这种方法不仅代码简洁，而且时间复杂度为O(L)，空间复杂度为O(1)，非常适合处理链表相关的问题。希望本文对你理解如何在Java中删除链表的倒数第N个节点有所帮助。