如何无需反复遍历删除含10000个节点链表的倒数第N个节点？

要实现无需反复遍历链表就能删除倒数第N个节点，**双指针（快慢指针）**是最优方案，只需要一次遍历即可完成操作，时间复杂度仍为O(n)但避免了两次独立遍历的开销。

核心思路 #

1. 初始化一个哑节点（dummy node），将其next指向链表头节点。这样可以统一处理删除头节点的边界情况，不用单独编写特殊判断逻辑。
2. 定义两个指针fast和slow，初始都指向哑节点。
3. 先让fast指针向前移动N步。
4. 同时移动fast和slow指针，直到fast指针走到链表末尾（fast.next为null）。此时slow指针的next指向的就是要删除的倒数第N个节点。
5. 调整slow的next指针，跳过目标节点完成删除操作。

代码示例（Python） #

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def removeNthFromEnd(head: ListNode, n: int) -> ListNode:
    dummy = ListNode(0, head)
    fast = dummy
    slow = dummy
    
    # 快指针先走n步
    for _ in range(n):
        fast = fast.next
    
    # 快慢指针同步移动，直到快指针抵达链表末尾
    while fast.next is not None:
        fast = fast.next
        slow = slow.next
    
    # 删除目标节点
    slow.next = slow.next.next
    return dummy.next

效率优势 #

对于10000个节点的链表，原方法需要先遍历10000次获取长度，再遍历10000-N次定位目标节点，总共涉及近20000次节点访问。而双指针方法仅需一次完整遍历（快指针走10000步，慢指针同步跟进），节点访问次数直接减半，实际运行效率明显更高。同时哑节点的使用简化了边界场景的处理，让代码更简洁健壮。

内容的提问来源于stack exchange，提问作者Pragati Rai