[数据结构与算法]力扣删除链表的倒数第N个节点

题目描述 ：

力扣删除链表的倒数第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个元素，所以我们可以先写一个辅助函数求取链表的长度，然后再定义一个前驱指针pre指向表头，再让前驱指针移动链表长减去n减一步到达待删除结点的前一个结点，再实现删除的操作!!!
• 思路2：(快慢双指针)我们避免求取链表长度，就分别让快慢指针分别指向头节点，第一次让快指针移动n次移动到距离尾节点相差n-1个节点的位置，也就是待删除节点的后一位！此时快指针与慢指针之间相差n个节点，再让慢指针和快指针同时移动，当快指针到底尾节点时停止，此时快慢指针均移动n-2步，也就是尾节点与第一次快指针指向节点之间相差的节点数目！！！。此时快指针与慢指针之间还是相差n个节点，由于第一次快指针与尾部节点相差n-2个节点，此时慢指针与指向尾部节点的快指针还是相差n个节点，所以此时的慢指针与快指针第一次指向的节点位置处相差n - (n-2) = 2个节点，但是我们是知道第一次移动快指针的位置是到待删除节点的下一位，所以**此时的慢指针就在待删除节点的前一位!!!*** ,（看下面的图示!!!）

代码块:

1.解法一代码块：

class Solution{
	public ListNode removeNthFromEnd(ListNode head, int n) {
		//定义前驱节点
		ListNode pre = head;
		int last = length(head) - n;
		//待删除的是头节点
		if (last == 0) {
			return head.next;
		}
		//将前去驱节点移动到待删除节点的前一个节点
		for (int i = 0; i < last - 1; i++) {
			pre = pre.next;
		}
		//删除操作
		pre.next = pre.next.next;
		return head;
	}
	//求取链表的长度
	private int length(ListNode head) {
		int len = 0
		while (head != null) {
			len++;
			head = head.next;
		}
		return len;
	}
}

2.解法二代码块：

class Solution {
	public ListNode removeNthFromEnd(ListNode head, int n) {
	//定义快慢指针,并均指向头节点
	ListNode fast = head;
	ListNode slow = head;
	
	//将fast移动n步，移动到待删除节点的下一位
	for (int i = 0; i < n; i++) {
		fast = fast.next;
		}
		//如果fast为空，表示删除的是头节点
		if (fast == null) {
			return head.next;
			}
		
		//fast与slow同时移动
		while(fast.next != null) {
			fast = fast.next;
			slow = slow.next;
		}
		//此处slow移动到待删除节点的前一位
		//删除操作
		slow.next = slow.next.next;
		return head;
	}
}

代码复杂度分析:

1.解法一:暴力遍历主要是求取链表的长度没有开辟额外的空间，所以时间复杂度为**O(N)**其中N为链表的长度，空间复杂度为O(1).
2.解法二:双指针法也平均时间复杂度为O(N),空间复杂度为:O(1).

做题感悟与总结:

对于双指针方法本人在学习了别人的方法后虽然可以以一个特例搞懂操作，但是别人的代码没有给出严格的证明，自己想那个数学证明也是花费了好多时间，只能说数理逻辑真的好重要。对于本题目一定要搞清楚指针是移动到了待删除节点还是其他的节点，对于链表的基本操作和概念一定要牢牢掌握!!!