题解 | #删除链表的倒数第n个节点#
删除链表的倒数第n个节点
https://www.nowcoder.com/practice/f95dcdafbde44b22a6d741baf71653f6
import java.util.*; /* * public class ListNode { * int val; * ListNode next = null; * public ListNode(int val) { * this.val = val; * } * } */ public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param head ListNode类 * @param n int整型 * @return ListNode类 */ public ListNode removeNthFromEnd (ListNode head, int n) { // write code here if (head == null || n <= 0) { return head; } // 创建一个虚拟头节点,方便处理删除头节点的情况 ListNode dummy = new ListNode(0); dummy.next = head; ListNode slow = dummy; ListNode fast = dummy; // 让 fast 指针领先 slow 指针 n+1 步 for (int i = 0; i <= n; i++) { if (fast == null) { return head; // 链表长度小于 n,不需要删除 } fast = fast.next; } // 同时移动 slow 和 fast 指针,直到 fast 指针到达链表末尾 while (fast != null) { slow = slow.next; fast = fast.next; } // 此时 slow 指向待删除节点的前一个节点 slow.next = slow.next.next; return dummy.next; // 返回新的头节点 } }
这个实现方式也是利用了快慢指针的原理,在一次遍历中找到倒数第 n 个节点的前一个节点,然后进行删除操作。通过引入一个虚拟头节点,可以更方便地处理删除头节点的情况。
在这个实现中,我们首先让 fast 指针领先 slow 指针 n+1 步,然后同时移动两个指针,直到 fast 指针到达链表末尾。这样 slow 指针就会指向倒数第 n 个节点的前一个节点,从而可以进行删除操作。
最后,返回虚拟头节点的下一个节点作为新的链表头。
注意,题目保证 n 一定是有效的,因此无需对 n 是否超出链表长度进行额外判断。