[python 刷题] 19 Remove Nth Node From End of List
题目：
题目说的是就是移除倒数第 n 个结点，如官方给的案例：
这里提供的 n 就是 2，也就是倒数第二个结点
这道题本身的难度不是很大，最简单的方法就是 2-pass，第一个循环找到链表的长度，随后循环到 n - 2 的长度即可，这个解法代码如下：
class Solution:
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
l, t = 0, head
while t:
l += 1
t = t.next
prev, next = head, head.next
while l - n - 1 > 0 and next:
prev = prev.next
next = next.next
n += 1
if l == n:
return head.next
if not next:
prev.next = None
return head
prev.next = next.next
return head
这么处理一下，其实边界条件挺多的（主要是当 n = 0 和 n = len(linked list) 这两个情况）
不过这道题有个 follow up：Could you do this in one pass?
也就是问一个循环能不能解决问题
这也是一个可以用双指针解决的方法，题目中说 nth from the emd，其实换个方式理解也可以理解成 nth from start:
这个时候的 fast 指向 3，slow 则是指向新建的 head，这里的差是 n + 1 是因为差第 n 个值是被移除的
这个时候 slow 和 fast 同时进入循环，当 fast 指向空时，slow 也指向了 n - 1 个值：
代码如下：
class Solution:
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
if not head:
return head
t = ListNode(0, head)
slow, fast = t, head
while n:
fast = fast.next
n -= 1
while fast:
slow = slow.next
fast = fast.next
slow.next = slow.next.next
return t.next
这里取 n = 1 反而是因为代码实现起来会方便一些，否则就要使用 while n - 1: 和 while fast.next: 结束循环：
class Solution:
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
if not head:
return head
t = ListNode(0, head)
slow, fast = t, head
while n - 1:
fast = fast.next
n -= 1
while fast.next:
slow = slow.next
fast = fast.next
slow.next = slow.next.next
return t.next
这两个代码从结果上来说是一样的
整体上来说，链表也好、二分搜索也好，这些 +1/-1 的边界条件其实就会影响代码会不会 AC