【完虐算法】删除链表倒数第n个节点【完虐算法】删除链表倒数第

更多算法题解，关注公众号《程序员学长》
删除链表倒数第n个节点问题描述
LeetCode 剑指 Offer II 021. 删除链表的倒数第 n 个结点
给定一个链表，删除链表的倒数第 n个结点，并且返回链表的头结点。
示例：
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

文章图片

分析问题
这个问题最简单的求解方式就是遍历一遍链表，获取到链表的长度m，然后求出倒数第n个结点的位置m-n+1，然后再遍历一次链表，找到第m-n+1的位置，删掉这个结点就好。其实，我们这里可以使用双指针法，只需要遍历一次链表就可以解决问题。
首先，我们可以设置两个指针slow和fast都指向头结点，然后让fast先走n步，之后slow和fast一起走，直到fast.next为空为止，这是slow指向的就是倒数第n+1个结点，我们通过slow.next=slow.next.next就可以把倒数第n个结点删掉。

文章图片

文章图片

文章图片

下面我们来看一下代码的实现。

def removeNthFromEnd(self,head,n): #左右指针指向头结点 slow = fast = head #fast先走n步 while n>0 and fast: fast = fast.next n=n-1if not fast: return head.nextwhile fast.next: slow = slow.next fast = fast.next slow.next = slow.next.next return head

【【完虐算法】删除链表倒数第n个节点】该算法只遍历一遍链表，所以时间复杂度是O(n)，空间复杂度是O(1)。