19. 删除链表的倒数第 N 个结点

题目链接：国际版，国内版
公司：Meta
解法：双指针

题目描述

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