⭐ 题目日期：

百度实习 - 2024/10/18

🌳 题目描述：

示例 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]

🧗难度系数：

⭐️ ⭐️ ⭐️

📝思路分析：

这道题考察删除链表中一个指定位置的节点。

1. 找到节点的位置：遍历链表，拿到 size，倒数第n个，也就是从头节点开始，第 size - n + 1 个
2. 引入哨兵节点(dummyNode): 由于头节点也可能被删除，我们引入哨兵节点，方便处理头节点被删除的情况
3. 找到被删除节点的前一个节点：从哨兵节点开始走 size - n 步，到达被删除节点的前一个节点 cur
4. 删除节点：将 cur 指向被删除节点(cur.next)的下一个节点 cur.next.next, 即将被删除节点剔除链表，cur.next = cur.next.next; 
5. 返回结果：返回(新)链表的头节点 dummyNode.next;

💻代码：

Java

 public ListNode removeNthFromEnd(ListNode head, int n) {
     if (head == null) {
         return null;
     }

     int size = listSize(head);
     ListNode dummyNode = new ListNode(0);
     dummyNode.next = head;
     ListNode cur = dummyNode;
     int steps = size - n;
     while (steps > 0) {
         steps--;
         cur = cur.next;
     }
     cur.next = cur.next.next;
     return dummyNode.next;
 }

 private int listSize(ListNode head) {
     int result = 0;
     ListNode cur = head;
     while (cur != null) {
         result++;
         cur = cur.next;
     }
     return result;
 }

🚵🏻复杂度分析：

时间复杂度：O(n)；n 为链表的长度，O(n)的时间遍历所有的节点拿到链表的大小，至多O(n) 遍历链表删除节点。

空间复杂度：O(1)

题目链接