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

本文介绍 LeetCode 第 19 题“删除链表的倒数第 N 个结点”的一种解法，使用字典存储节点位置，实现一次遍历完成删除。

Leetcode 链表 Python 哈希表

阅读要点

题目要求一次遍历删除倒数第 N 个节点
使用字典存储每个节点的位置
处理边界情况：链表为空、只有一个节点、删除头节点

题目

19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）

解法

看到题目，最容易想到的方法是遍历两次链表：第一次统计链表长度，第二次找到待删除节点的前驱节点进行删除。但题目要求只通过一次遍历，因此我们需要更巧妙的方法。

这里我们使用字典来存储每个节点的位置。具体做法是：遍历链表，将每个节点按索引存入字典，同时记录链表长度。遍历结束后，我们可以通过索引直接定位到倒数第 N 个节点及其前驱节点，从而实现一次遍历完成删除。

这种方法的时间复杂度为 O(n)，空间复杂度为 O(n)，因为需要存储所有节点。虽然空间复杂度较高，但满足了一次遍历的要求。

答案

# 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]:
        if not head:
            return head
        if not head.next:
            head = None
            return head
        mp = collections.defaultdict()
        temp = head
        count = 0
        while temp:
            mp[count] = temp
            count += 1
            temp = temp.next
        temp = mp[count - n]
        if count - n > 0:
            if count - n - 1 >= 0:
                mp[count - n - 1].next = temp.next
            temp.next = None
        else:
            head = head.next
        return head

复杂度分析

时间复杂度：O(n)，其中 n 是链表长度。我们只遍历了一次链表。
空间复杂度：O(n)，因为使用了字典存储所有节点。

边界情况

链表为空：直接返回空。
链表只有一个节点：删除后链表为空。
删除头节点：需要移动头指针。

待补充

如果要求空间复杂度 O(1)，可以使用双指针法，但本文不展开。