力扣热搜一百题之19.删除链表的倒数第n个节点

本文主要是介绍力扣热搜一百题之19.删除链表的倒数第n个节点，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述：

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

示例：

给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后，链表变为 1->2->3->5.

说明：

给定的 n 保证是有效的。

解题思路：

1.找到倒数第n+1个节点；
2.把这个节点的next节点指向next.next。
先看数组：如果该题的数据结构不是链表而是数组的话，寻找倒数第n+1个节点时是不是就非常简单？，直接利用数据的长度和传进来的n，找到倒数第n+1个数，只是删除时，需要重新创建数组，操作稍微有些复杂，想了解详情的可以去看ArrayList的remove操作。
再看链表：链表的删除节点操作是不是很简单？只是难在如何找到倒数第n+!个节点，刚好综合数组的特点，利用数组的思想，找到倒数第n+1个节点即可，然后进行删除。

首先创建一个哑节点，并将此节点的next指向head节点，创建哑节点的目的是防止出现链表只有一个节点的情况。

方法一：创建一个指针指向head节点，先遍历一次链表，得出链表的长度lenth，然后把指针指到哑节点，再次遍历链表，让指针走length-n次，此时因为是从哑节点开始走，所以刚好在length-n次后，指针停在倒数第n+1个节点上，所以将这个节点的next节点指向next.next即可。
时间复杂度：O（n），代码：

public static ListNode removeNthFromEnd01(ListNode head, int n){//创建一个哑节点ListNode dummy = new ListNode(0);dummy.next = head;ListNode index = head;int length = 0;//第一次遍历链表，得出链表长度while (index != null){length++;index = index.next;}index = dummy;for (int i = 0; i < length - n; i++) {index = index.next;}index.next = index.next.next;return dummy.next;}

方法二：双指针，省略遍历链表得出长度的步骤。首先将两个指针都指向哑节点，然后第一个指针先往下走n+1步，以便后续找到倒数n+1个节点，然后两个指针同时往下走，直到第一个指针指向空节点时停止，此时刚好第二个指针指向倒数第n+1个节点，最后进行删除操作即可。
时间复杂度：O（n），代码：

public static ListNode removeNthFromEnd02(ListNode head, int n) {ListNode dummy = new ListNode(0);dummy.next = head;ListNode first = dummy;ListNode second = dummy;//使两个指针之间的距离为n+1，以便后续找到倒数n+1个节点for (int i = 0; i < n+1; i++) {first = first.next;}//两个指针同时往下走，直到第一个指针指向队尾（null）时停止，// 此时刚好第二个指针指向倒数第n+1个节点while (first != null){first = first.next;second = second.next;}second.next = second.next.next;return dummy.next;}