题目
- 主要有三个思路解决这个问题：
- 第一个最普通的思路，获取链表长度，再操作len-n+1次，定位到被删除节点的前一个
- 第二个思路，用栈，先让所有链表元素入栈，再一个一个退出，后入先出嘛，完美的工具
- 第三个思路，我最爱的双指针，让俩指针相隔n个位置，这样前面的指针到头的时候，后面那个指针就刚好到要删除的那个节点的前一个，当然实现这样的想法还需要引入哑结点
- 前两个方法也引入，这样可以让头结点普通化，否则还要对节点是否是头结点单独讨论
栈的方法
class Solution:
def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
dummy = ListNode(0, head)
stack = list()
cur = dummy
while cur:
stack.append(cur)
cur = cur.next
for i in range(n):
stack.pop()
prev = stack[-1]
prev.next = prev.next.next
return dummy.next
- 这里说一下，好像python里的栈是通过list实现的
- list有append函数，还有pop函数呢
双指针
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.next = second.next.next
return dummy.next
注意：first是从head开始，而second从哑结点dummy开始的，为啥为这样呢，因为first要到None才退出循环，这个时候其实多操作了一次，如果second也从head开始，那就到了要删除的节点那了
