[数据结构与算法]删除链表的倒数第n个（python）

坑：
1.python2居然不能在函数里面定义函数
2.不是很会如何在python中创建一个值相等的变量，但是内存地址不一样
3.debug了一下，发现python的=是引用，而python则是另起存储地址
4.要设置头节点dummy = ListNode(0, head)

方法1：求出len后，找到第len - n个即可：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        
        def getlen(head: ListNode):
            cnt = 0
            while head != None:
                cnt += 1
                head = head.next
            return cnt

        len = getlen(head)
        dummy = ListNode(0, head)
        cur = dummy
        for i in range(1, len - n + 1):
            cur = cur.next
        
        cur.next = cur.next.next
        return dummy.next

head可能分分钟没掉，但是dummy是yyds永远都在的，我们永远相信dummy，所以要从dummy开始

法二：快慢指针

快指针先走n步，然后快慢同时起步知道快指针到达终点

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        
        dummy = ListNode(0, head)
        first = head
        second = dummy

        for i in range(n):
            first = first.next

        while first:
            first = first.next
            second = second.next
        
        #这时second是去到要删除的前一个位置
        second.next = second.next.next
        return dummy.next

最后的位置是要删除的前一个位置哦！

总结
难点就是引入dummy，以及cur.next.next中cur.next已经为None怎么处理？