给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
提示：
链表中结点的数目为 sz
- 1 <= sz <= 30
- 0 <= Node.val <= 100
- 1 <= n <= sz
你能尝试使用一趟扫描实现吗？
具体实现
要删除链表的倒数第 n 个节点，并返回链表的头节点，我们可以使用一趟扫描的方法来实现。这个方法涉及使用两个指针：快指针和慢指针。快指针先向前移动 n 步，然后慢指针从链表的头节点开始，与快指针同时移动。当快指针到达链表的末尾时，慢指针所在的下一个节点就是倒数第 n 个节点。
以下是使用 Java 实现的删除链表倒数第 n 个节点的函数：
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;
// 快指针先走 n 步
for (int i = 0; i < n; i++) {
fast = fast.next;
}
// 快慢指针同时移动，直到快指针指向链表的末尾
while (fast.next != null) {
fast = fast.next;
slow = slow.next;
}
// 慢指针的下一个节点就是倒数第 n 个节点，删除它
slow.next = slow.next.next;
return dummy.next; // 返回哑节点的下一个节点，即新的头节点
}
}
使用示例：
public class Main {
public static void main(String[] args) {
// 示例 1
ListNode head1 = new ListNode(1);
head1.next = new ListNode(2);
head1.next.next = new ListNode(3);
head1.next.next.next = new ListNode(4);
head1.next.next.next.next = new ListNode(5);
int n1 = 2;
ListNode newHead1 = new Solution().removeNthFromEnd(head1, n1);
printList(newHead1); // 应该输出 [1,2,3,5]
// 示例 2
ListNode head2 = new ListNode(1);
int n2 = 1;
ListNode newHead2 = new Solution().removeNthFromEnd(head2, n2);
printList(newHead2); // 应该输出 []
// 示例 3
ListNode head3 = new ListNode(1);
head3.next = new ListNode(2);
int n3 = 1;
ListNode newHead3 = new Solution().removeNthFromEnd(head3, n3);
printList(newHead3); // 应该输出 [1]
}
private static void printList(ListNode head) {
while (head != null) {
System.out.print(head.val + " ");
head = head.next;
}
System.out.println();
}
}
代码输出结果与题目中的示例输出是一致， V 哥的这个实现中，使用了一个哑节点来简化边界条件的处理，这样即使要删除的是头节点，代码也能正常工作。这个方法只需要一趟扫描，因此时间复杂度是 O(sz)，其中 sz 是链表的长度。
实现过程和步骤如下
下面 V 哥把实现过程再详细说明一下，为了帮助你更好的理解代码的逻辑实现：
- 创建一个哑节点（dummy node），并将其设置为链表的头节点之前的一个节点。哑节点的引入是为了简化边界条件的处理，特别是当需要删除的节点是头节点时。
- 初始化两个指针：快指针（fast）和慢指针（slow），它们都指向哑节点。
- 快指针先向前移动 n 步。这样，快指针和慢指针之间就保持了 n 个节点的距离。
- 快指针和慢指针同时向前移动，直到快指针到达链表的末尾（即快指针的下一个节点为 null）。此时，慢指针的位置就是倒数第 n 个节点的前一个节点。
- 修改慢指针的 next 指针，使其指向下一个节点的下一个节点，从而跳过倒数第 n 个节点，实现删除操作。
- 返回哑节点的下一个节点，即新的头节点。
这个方法的核心思想是利用快慢指针的差距来找到倒数第 n 个节点。快指针先走 n 步，然后快慢指针一起移动，直到快指针到达链表末尾。此时，慢指针所在的位置就是倒数第 n 个节点的前一个节点，这样就可以很容易地删除倒数第 n 个节点。
小结
V哥经过测试，坐实了这个方法只需要一趟扫描，所以时间复杂度是 O(sz)，其中 sz 是链表的长度。空间复杂度是 O(1)，因为只需要常数级别的额外空间来存储快慢指针和哑节点。
