关于leetcode:完虐算法删除链表倒数第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-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)。