【刷穿 LeetCode】19. 删除链表的倒数第 N 个结点（中等）

要删除链表的倒数第 N 个结点，可以使用快慢指针的方法，只需一次扫描即可完成。以下是详细的解答：

方法思路

初始化指针：使用两个指针 slow 和 fast，初始时都指向链表的头节点 head。
移动快指针：先让 fast 指针向前移动 N 步，这样 fast 和 slow 之间就相隔 N 个节点。
处理边界情况：如果 fast 在移动 N 步后变为 null，说明要删除的是头节点，直接返回 head.next。
同时移动两个指针：然后同时移动 slow 和 fast，直到 fast 到达链表的最后一个节点。此时 slow 指向待删除节点的前一个节点。
删除节点：修改 slow.next 指向 slow.next.next，从而跳过待删除节点。
返回头节点：返回修改后的链表头节点。

解决代码class ListNode { int val; ListNode next; ListNode() {} ListNode(int val) { this.val = val; } ListNode(int val, ListNode next) { this.val = val; this.next = next; }}class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { ListNode dummy = new ListNode(0); dummy.next = head; ListNode slow = dummy; ListNode fast = dummy; // 快指针先走n步 for (int i = 0; i <= n; i++) { fast = fast.next; } // 快慢指针同时前进，直到快指针到达末尾 while (fast != null) { slow = slow.next; fast = fast.next; } // 删除慢指针的下一个节点 slow.next = slow.next.next; return dummy.next; }}代码解释

初始化虚拟头节点：创建一个虚拟头节点 dummy，其 next 指向 head，这样可以方便处理删除头节点的情况。
快指针移动：快指针 fast 先移动 N+1 步，这样当 fast 到达链表末尾时，slow 正好指向待删除节点的前一个节点。
同步移动指针：然后同时移动 slow 和 fast，直到 fast 为 null，此时 slow 指向待删除节点的前一个节点。
删除节点：通过修改 slow.next 的指向，跳过待删除节点，完成删除操作。
返回结果：返回 dummy.next，即修改后的链表头节点。

这种方法确保了一次扫描完成操作，时间复杂度为 O(L)（L 为链表长度），空间复杂度为 O(1)。

您可能感兴趣问答

Collapsible

热门标签

热点问答