关于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)。