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

- 1. 题目介绍
- 2. 方法一：计算链表长度
- - 逻辑流程:
  - 代码
  - 复杂度分析

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;
    }
}