【leetcode】19. Remove Nth Node From End of List解题报告

删除链表倒数第n个元素

毫无疑问要用快慢指针法，然快指针先走n步，然后满指针再走。
不过这里要注意的是，比如例子中要删除节点4，那么慢指针要停留在节点3，这样才能删除下一个节点 。那么当要删除第一个节点的时候，因为没有上一个节点 。所以要新建一个新的节点，作为新的头部

class Solution(object):
    def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """
        new_head =  ListNode(-1)
        new_head.next = head
        fast = new_head
        slow = new_head
        while(n >= 0):
            fast = fast.next
            n -=1
        while(fast != None):
            slow = slow.next
            fast = fast.next
        if slow.next  != None:
          slow.next = slow.next.next
        return new_head.next

这样的写法引入了一个新的节点，总感觉不太好，可以采取下面的方法来在引入新头节点的情况下完成任务
举个例子：[1,2] ,2
要删除第一个节点 ，因为快指针走两步就到None了，并且给的n都是有效的，我们可以判断当fast指针走n步达到None的话，那么要删除的元素肯定是链表的头结点，那么返回head.next即可

class Solution(object):
    def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """
        fast = head
        slow = head
        while(n > 0 and fast!=None):
            fast = fast.next
            n -=1
        if fast == None:
            return head.next
        while(fast.next != None):
            fast= fast.next
            slow = slow.next
        if slow.next !=None:
          slow.next = slow.next.next
        return head