每日一题：删除链表的倒数第 N 个结点

要删除链表的倒数第N个结点，可以使用双指针技巧。以下是详细的解题思路和代码实现：

解题思路

创建虚拟头节点：为了方便处理删除头节点的情况，创建一个虚拟头节点dummy，其next指向真正的头节点head。
初始化指针：定义两个指针left和right，初始时都指向dummy。
移动右指针：先将right指针向右移动n步，这样left和right之间相隔n个节点。
同步移动指针：然后同时移动left和right指针，直到right指向链表末尾（即right.next为null）。此时，left指向要删除节点的前一个节点。
删除节点：通过left.next = left.next.next删除目标节点。
返回结果：返回dummy.next，即新的头节点。

代码实现（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(-1); dummy.next = head; ListNode left = dummy; ListNode right = dummy; // 移动右指针n步 for (int i = 0; i < n; i++) { right = right.next; } // 同步移动左右指针，直到右指针到达末尾 while (right.next != null) { left = left.next; right = right.next; } // 删除目标节点 left.next = left.next.next; return dummy.next; }}复杂度分析

时间复杂度：O(n)，其中n是链表的长度。我们只需要遍历链表两次（移动右指针和同步移动指针）。
空间复杂度：O(1)，只使用了常数级别的额外空间。

示例验证

示例1：
输入：head = [1,2,3,4,5], n = 2
过程：
初始：dummy -> 1 -> 2 -> 3 -> 4 -> 5
移动right 2步：right指向2。
同步移动left和right直到right.next为null：
left移动到3，right移动到4。
left移动到4，right移动到5。
删除left.next（即5的前一个节点4的下一个节点5）：4 -> null变为4.next = 5.next（即null）。
输出：[1,2,3,5]
示例2：
输入：head = [1], n = 1
过程：
初始：dummy -> 1
移动right 1步：right指向1。
同步移动left和right直到right.next为null：
left和right都指向1，但right.next为null，循环结束。
删除left.next（即1）：dummy.next = 1.next（即null）。
输出：[]
示例3：
输入：head = [1,2], n = 1
过程：
初始：dummy -> 1 -> 2
移动right 1步：right指向1。
同步移动left和right直到right.next为null：
left移动到1，right移动到2。
删除left.next（即2）：1.next = 2.next（即null）。
输出：[1]

关键点

虚拟头节点：简化删除头节点的操作。
双指针间隔：通过间隔n步确保left指向目标节点的前一个节点。
同步移动：确保right到达末尾时，left位置正确。

这种方法高效且易于理解，适用于大多数链表操作问题。

您可能感兴趣问答

Collapsible

热门标签

热点问答