题目描述
Given the head of a linked list, remove the nth node from the end of the list and return its head.
Example 1:
Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]
Example 2:
Input: head = [1], n = 1
Output: []
Example 3:
Input: head = [1,2], n = 1
Output: [1]
思路
题目要求我们删除链表的倒数第 N 个结点，并且在 follow up 中明确指出只能用一次遍历，因此先完整遍历一遍链表求出链表总长度的做法就不可取了。这里我们假设链表的总长度是 L，删除链表的倒数第 N 个结点，等同于删除链表的正数第 L - N 个结点。我们可以使用快慢指针，即：快指针先走 N 步，此时慢指针留在头结点不动。当快指针走过第 N 个结点之后，慢指针再开始移动。当快指针到达链表末尾的时候，慢指针也停止移动，则慢指针停止的位置就是我们想要的结点。
从数学的角度来看上述思路，可以归纳为：快指针先走了 N 步，则剩余距离为 L - N。之后快慢指针一起走，则快指针到达链表末尾的时候，慢指针走过的距离也为 L - N，而第 L - N 个结点恰好就是我们想要的那个结点。复杂度分析也很简单，我们通过一次遍历即得到了解，并且没有申请额外的空间，因此时间复杂度为 O(N), 空间复杂度为 O(1)
参考代码
# 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: Optional[ListNode], n: int) -> Optional[ListNode]:
# 快慢指针, 一个 fast 一个 slow, fast 指针先走 n 步, 之后两个指针再一起走
slow, fast = head, head
while n > 0:
fast = fast.next
n -= 1
# edge case, 如果 fast 指针已经到头了直接返回 slow 的下一个元素即可
if not fast:
return slow.next
while fast.next:
slow = slow.next
fast = fast.next
slow.next = slow.next.next
return head
