题目

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

输入：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

思路

• 双指针
• 虚拟头节点
• 一次遍历解决链表查找倒数节点，可以采用双指针。

解答

//给你一个链表，删除链表的倒数第 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 
// 
//
// 
//
// 进阶：你能尝试使用一趟扫描实现吗？ 
//
// Related Topics 链表 双指针 👍 2822 👎 0//leetcode submit region begin(Prohibit modification and deletion)
/*** 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) {/*** 首先找倒数第k个节点* 然后删除*///虚拟头节点ListNode dummy=new ListNode();dummy.next=head;//把虚拟头节点放在前面//找到倒数第N个节点ListNode x=findFromEnd(dummy,n+1);//n+1代表长度//删掉倒数第n个节点x.next=x.next.next;return dummy.next;}//查找倒数第K个节点的位置ListNode findFromEnd(ListNode head,int k){ListNode p1=head;//p1先走k步for (int i=0;i<k;i++){p1=p1.next;}ListNode p2=head;//p1和p2同时走n-k步，p2停留的就是倒数第k步while (p1!=null){p2=p2.next;p1=p1.next;}return p2;}
}
//leetcode submit region end(Prohibit modification and deletion)