【Leetcode】19. 删除链表的第N个节点

1. 题目介绍

题目描述

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

示例 1：

• 输入：head = [1,2,3,4,5], n = 2

• 输出：[1,2,3,5]

示例 2：

• 输入：head = [1], n = 1
• 输出：[]

示例 3：

• 输入：head = [1,2], n = 1
• 输出：[1]

提示

• 链表中结点的数目为 sz
• 1 <= sz <= 30
• 0 <= Node.val <= 100
• 1 <= n <= sz

2. 方法一：计算链表长度

逻辑流程:

• 输入是一个链表

1 -> 2 -> 3 -> 4 -> None

• 创建一个虚拟头结点 dummy，它的 next 指向链表的实际头结点 head。
  这一步是为了处理边缘情况，比如当要删除的是头节点时，可以避免额外的条件判断。

dummy -> 1 -> 2 -> 3 -> 4 -> None

其中 dummy 是一个虚拟头结点，它的 next 指向实际的头结点 1。

• 调用辅助函数 getLength 来计算整个链表的长度。
• 初始化一个指针 cur，指向 dummy。
  这个指针将用来遍历链表，直到找到待删除节点的前一个节点。
  如果执行了 ListNode cur = dummy;，那么 cur 也指向 dummy 所指向的那个节点。
  此时，cur 和 dummy 的关系如下：

dummy (cur) -> 1 -> 2 -> 3 -> 4 -> None

• 使用一个循环，使 cur 向后移动 length - n + 1 次，这样 cur 就会停在待删除节点的前一个位置。
  如果执行 cur = cur.next;，cur 将移动到下一个节点 1：

dummy     (cur)↓1 -> 2 -> 3 -> 4 -> None

• 更新 cur.next 为 cur.next.next，跳过当前的下一个节点（即待删除节点）。
  如果执行 cur.next = cur.next.next;，这将跳过节点 2，并让 1 直接指向 3：

dummy     (cur)↓1  ->  3 -> 4 -> None|  /   |2  \   |\  |\ |4

• 最后，返回 dummy.next 作为新的头节点，这是因为如果删除了原始的头节点，那么新的头节点就是 dummy.next。
  在这个过程中，dummy 的 next 指针也被更新了，因为 cur 和 dummy 指向同一个节点。所以，dummy 的 next 也从 1 变成了 3。

代码

class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {ListNode dummy = new ListNode(0, head);int length = getLength(head);ListNode cur = dummy;for (int i = 1; i < length - n + 1; ++i) {cur = cur.next;}cur.next = cur.next.next;ListNode ans = dummy.next;return ans;}public int getLength(ListNode head) {int length = 0;while (head != null) {++length;head = head.next;}return length;}
}

复杂度分析

• 时间复杂度：O(L)，其中 L 是链表的长度。

• 空间复杂度：O(1)。