删除链表的倒数第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; } }