力扣刷题Day 31：删除链表的倒数第N个结点（19）

1.题目描述

2.思路

方法1：两遍遍历，第一遍获取链表长度，第二遍到达指定位置删除指定结点。

方法2：递归，一趟扫描即可实现，但可能是因为我的思路太混乱，代码很繁琐而且空间复杂度也很高。

方法3：跟灵茶山艾府大佬学习的双指针方法。

3.代码（Python3）

方法1：

class Solution:def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:node = headlist_len = 0while node:list_len += 1node = node.nextnode = headif (list_len - n) == 0:return head.nextelif (list_len - n) != 1:for i in range(list_len - n - 1):node = node.nextnode.next = node.next.nextreturn head

方法2：

class Solution:def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:def helper(node):# 获取链表长度nonlocal list_lenlist_len += 1if not node.next:return (1, node, False)cur_n, next_node, find_or_not = helper(node.next)if cur_n == n + 1:if not find_or_not:find_or_not = Truereturn (cur_n, next_node, find_or_not)else:if list_len - n == 1:find_or_not = Truereturn (cur_n + 1, node, find_or_not)list_len = 0prior_node, find_or_not = helper(head)[1:]if find_or_not:if list_len - n == 1:prior_node = headprior_node.next = prior_node.next.nextreturn headelse:return head.next

方法3：

class Solution:def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:left = right =dummy = ListNode(next=head)for _ in range(n):right = right.nextwhile right.next:left, right = left.next, right.nextleft.next = left.next.nextreturn dummy.next

4.执行情况

方法1：

方法2：

方法3：

5.感想

两趟扫描竟然比一趟扫描的性能还要好一些。