更多题解，请关注公众号：程序员学长，让你进大厂不走弯路

删除链表倒数第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)。