删除链表的倒数第N个节点 力扣19

一、题目

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

二、思路

           1.容易想到的思路就是先遍历一遍链表统计长度，倒数第n个节点就是正数的第len - n + 1个节点。要删除该节点，我们要找到len - n的节点，即可删除。

            2.经典思路：删除倒数第n个节点，让fast移动n步，然后让fast和slow同时移动，直到fast指向链表末尾。删掉slow所指向的节点就可以了。为了统一头节点和其他节点的删除操作，使用虚拟头节点。

三、代码

        暴力解：

public class Test {public static void main(String[] args) {Scanner sc = new Scanner(System.in);System.out.println("请输入链表的元素，输入非数字结束：");ListNode head = new ListNode(sc.nextInt());ListNode current = head;while (sc.hasNextInt()) {ListNode node = new ListNode(sc.nextInt());current.next = node;current = current.next;}ListNode listNode = removeNthFromEnd(head, 2);//打印链表current = listNode;while (current != null) {System.out.print(current.val + " ");current = current.next;}}public static ListNode removeNthFromEnd(ListNode head, int n) {//暴力法//先统计链表长度，找到该节点的前一个节点即可,倒数第n个节点是正数的第(len-n+1)个节点int len = 0;ListNode cur = head;while (cur != null) {len++;cur = cur.next;}//如果只有一个元素if(len == 1){return null;}// 如果需要删除头节点if (len - n == 0) {return head.next;}cur = head;//找到第len-n+1个节点的前一个节点for (int i = 1; i < len - n; i++) {cur = cur.next;}cur.next = cur.next.next;return head;}
}

       双指针法：

        

class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {//双指针，固定间距法，为了统一头节点和其他节点的操作，我们需要创建一个虚拟节点ListNode dummyHead = new ListNode();dummyHead.next = head;//快慢指针指向虚拟头节点ListNode fastIndex = dummyHead;ListNode slowIndex = dummyHead;//先让快指针走n+1 步再同时移动，这里为什么是n+1 呢？//因为我们在删除节点的时候要找到前一个节点，//将区间扩大到n+1，那么当快指针为空时，慢指针才能到达被删除节点的前一个节点for(int i = 0; i<= n;i++) {fastIndex = fastIndex.next;}while(fastIndex != null) {  //快慢指针同时移动fastIndex = fastIndex.next;slowIndex = slowIndex.next;}// 检查 slowIndex.next 是否为 null，以避免空指针异常if (slowIndex.next != null) {slowIndex.next = slowIndex.next.next;}return dummyHead.next;}
}