19. 删除链表的倒数第N个节点
难度中等1087收藏分享切换为英文接收动态反馈
给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
示例：
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.说明：
给定的 n 保证是有效的。
进阶：
你能尝试使用一趟扫描实现吗？
通过次数274,931
提交次数679,764
题解
解题思路
本题解采用了 双指针 的思想：
只需要使得 快指针 比 慢指针 快 n个节点 就行
之后两个指针同时向后遍历。直到 快指针 到达 链表的最后一个元素，慢指针 即 目标元素
但是需要注意的一点是：
为了防止 删除目标节点 导致 空指针异常，我们需要为原串增加一个 头节点
/**
* 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) {
if( n < 1 || head == null) return head;
ListNode pre = new ListNode();
pre.next = head;
ListNode slow = pre;
ListNode fast = pre;
for(int i = 0; i < n+1; i++){
fast = fast.next;
}
while( fast != null){
fast = fast.next;
slow = slow.next;
}
slow.next = slow.next.next;
return pre.next;
}
}转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 mym_74@163.com