链表问题：删除倒数第N个节点

"删除链表倒数第N个节点" 在链表数据结构中，删除特定位置的节点是一项常见的操作。本题目的目标是删除链表的倒数第N个节点，即从链表尾部开始数的第N个节点，并返回修改后的链表头结点。题目给出的例子是删除链表1->2->3->4->5中的倒数第二个节点（即节点4），结果链表变为1->2->3->5。 ### 解题思路与方法 #### 1. 双指针法 为了解决这个问题，我们可以使用双指针法。这种方法的关键在于创建两个指针，一个称为`first`，另一个称为`second`。首先，`first`指针会向前移动n+1个节点，这样它就位于倒数第N个节点的前一个位置。然后，`second`指针从头结点开始，保持与`first`指针的距离始终为n个节点。当`first`指针到达链表尾部时，`second`指针就会指向倒数第N个节点。 #### 2. 实现步骤 - 初始化一个虚拟头结点`dummy`，将其`next`指向实际的头结点`head`，这样可以简化边界条件的处理。 - 设置`dummy`和`head`为`first`和`second`指针的初始值。 - 使用一个循环，使`first`指针向前移动n+1次，以便它们之间的距离为n个节点。 - 当`first`指针到达链表末尾（即`first`为`null`）时，`second`指针指向的就是倒数第N个节点。 - 修改`second`指针的`next`属性，使其指向原`second.next.next`，这样就跳过了我们要删除的节点。 - 返回`dummy.next`作为新的链表头结点。 ### 代码实现 ```java public ListNode removeNthFromEnd(ListNode head, int n) { ListNode dummy = new ListNode(0); dummy.next = head; ListNode first = dummy; ListNode second = dummy; // Advances first pointers so that the gap between first and second is n nodes apart for (int i = 1; i <= n + 1; i++) { first = first.next; } // Move first to the end, maintaining the gap while (first != null) { first = first.next; second = second.next; } second.next = second.next.next; return dummy.next; } ``` ### 复杂度分析 - **时间复杂度**：O(L)，其中L是链表的长度。算法对链表进行了一次遍历，所以时间复杂度是线性的。 - **空间复杂度**：O(1)，我们仅使用了常量级别的额外空间，包括两个指针和一个虚拟头结点。 通过双指针法，我们可以在遍历链表一次的情况下完成删除操作，实现了时间复杂度的优化。这种方法在处理链表问题时非常常见，尤其是在需要定位特定位置节点的场景下。