题目

给你一个链表，删除链表的倒数第 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)