题目

• 主要有三个思路解决这个问题：
• 第一个最普通的思路，获取链表长度，再操作len-n+1次，定位到被删除节点的前一个
• 第二个思路，用栈，先让所有链表元素入栈，再一个一个退出，后入先出嘛，完美的工具
• 第三个思路，我最爱的双指针，让俩指针相隔n个位置，这样前面的指针到头的时候，后面那个指针就刚好到要删除的那个节点的前一个，当然实现这样的想法还需要引入哑结点
  • 前两个方法也引入，这样可以让头结点普通化，否则还要对节点是否是头结点单独讨论

栈的方法

class Solution:def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:dummy = ListNode(0, head)stack = list()cur = dummywhile cur:stack.append(cur)cur = cur.nextfor i in range(n):stack.pop()prev = stack[-1]prev.next = prev.next.nextreturn dummy.next

• 这里说一下，好像python里的栈是通过list实现的
• list有append函数，还有pop函数呢

双指针

class Solution:def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:dummy = ListNode(0, head)first = headsecond = dummyfor i in range(n):first = first.nextwhile first:first = first.nextsecond = second.nextsecond.next = second.next.nextreturn dummy.next

注意：first是从head开始，而second从哑结点dummy开始的，为啥为这样呢，因为first要到None才退出循环，这个时候其实多操作了一次，如果second也从head开始，那就到了要删除的节点那了