LeetCode热题100--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]

2. 题解

/*** Definition for singly-linked list.* public 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;int length = 0;ListNode current = head;while( current != null){length++;current = current.next;}int index = length - n;current = dummy;for(int i = 0; i < index; i++){current = current.next;}current.next = current.next.next;return dummy.next;}
}

3. 解析

出自：沉默王二

1. public ListNode removeNthFromEnd(ListNode head, int n) {…} 这是一个名为removeNthFromEnd的方法，它接受两个参数head和n，分别代表链表头部和要移除的节点的索引。

2. 2-5: ListNode dummy = new ListNode(0); dummy.next = head; int length = 0; ListNode current = head; while(current != null){length++; current = current.next;} 这是初始化部分，创建了一个新的虚拟节点dummy并将其链接到原始头部。然后计算了链表的长度。

3. 6-10: int index = length - n; current = dummy; for(int i = 0; i < index; i++){current = current.next;} 这是寻找要移除节点的前一个节点的部分，通过遍历到正确的索引位置。

4. 11: current.next = current.next.next; 这行代码是实际的移除操作，将倒数第n个节点与其后面的节点断开连接，从而将其从链表中移除。

5. 12: return dummy.next; 最后返回的是新的头部（可能已经发生了改变）。这是因为我们在原始链表的头部之前添加了一个虚拟节点dummy来处理边界情况（例如当我们需要删除的是第一个元素时），所以在最终结果中不会丢失任何信息。

6. 整个函数的作用是从给定的链表中移除倒数第n个节点并返回修改后的头部。它首先计算出链表的长度，然后找到要删除的节点的前一个节点的位置，最后进行实际的删除操作。这种方法的时间复杂度为O(N)，其中N是链表的长度。