更多算法题解，关注公众号《程序员学长》

删除链表倒数第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-1                    if not fast:            return head.next                while fast.next:            slow = slow.next            fast = fast.next        slow.next = slow.next.next        return head

该算法只遍历一遍链表，所以工夫复杂度是O(n)，空间复杂度是O(1)。