引用自：19. 删除链表的倒数第 N 个结点（如有侵权联系删除）
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
示例 1：
输入：head = [1,2,3,4,5], n = 2 输出：[1,2,3,5]
示例 2：
输入：head = [1], n = 1 输出：[]
示例 3：
输入：head = [1,2], n = 1 输出：[1]
提示：
- 链表中结点的数目为 sz
- 1 <= sz <= 30
- 0 <= Node.val <= 100
- 1 <= n <= sz
进阶： 你能尝试使用一趟扫描实现吗？
解题：没什么好说的(‘狗头’)，
方法一(两次遍历(扫描))：
第一次遍历求出链表长度总长度length，
第二次找到倒数第n+1个节点，因为要想删除第n个节点Node_delete，需要找到它的上一个节点Node_delete_before，然后：
Node_delete_before.next = Node_delete_before.next.next
即，让Node_delete_before指向的下一个节点，等于Node_delete_before的下一个(Node_delete)的下一个(Node_delete的下一个)，这样，就相当于把Node_delete给删除(跳过去)掉了。
方法二（一次递归扫描，直接拿到倒数第n+1个节点）
可以先设置一个全局变量计数器K = n+1，然后每次递归的方式往后走，当走到最后一个节点的时候，开始return，并且每次return之前需要将K-1，然后判断，K是否等于0，当K等于0了，说明这是倒数第K个节点，则将这个节点的自己返回到上一层，否则说明不是倒数第K个节点，则将下一层传上来的指针接着往上抛就好了(因为用的Python所以全局变量直接用了一个list表示)。
方法一：
略了，这个好写
方法二
class Solution:
def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
if head == None:
return None
k = [n+1]
n_before = self.recursive_search(head, [n+1])
if n_before is None:
head = head.next
return head
else:
n_before.next = n_before.next.next
return head
def recursive_search(self, head, k):
if head.next is not None:
temp = self.recursive_search(head.next, k)
k[0] -= 1
if k[0] != 0:
return temp
elif k[0] == 0:
return head
else:
k[0] -= 1
return None
测试：
# 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:
if head == None:
return None
k = [n+1]
n_before = self.recursive_search(head, [n+1])
if n_before is None:
head = head.next
return head
else:
n_before.next = n_before.next.next
return head
def recursive_search(self, head, k):
if head.next is not None:
temp = self.recursive_search(head.next, k)
k[0] -= 1
if k[0] != 0:
return temp
elif k[0] == 0:
return head
else:
k[0] -= 1
return None
def trans(array_to_link):
if len(array_to_link) == 0:
return None
head = None
temp = None
for i in range(len(array_to_link)):
if i == 0:
head = ListNode(array_to_link[i], None)
temp = head
else:
temp.next = ListNode(array_to_link[i],None)
temp = temp.next
return head
def print_link(head):
if head == None:
print('link is None')
return
temp = head
while temp is not None:
print(temp.val)
temp = temp.next
if __name__ == '__main__':
head = trans([1,2,3,4,5,6,7])
print("head_link: [1,2,3,4,5,6,7], n = 7")
so = Solution()
head = so.removeNthFromEnd(head,7)
print_link(head)
总结：
虽然会写，但是还是想了一会，耽误了一点时间，所以还是要经常刷题，才不会生疏。
