第60天：Python 删除链表倒数第N个节点，双指针技巧一次遍历删除（LeetCode #19 风格）

Source: Dev.to

第 60 天 – 删除链表倒数第 N 个节点

欢迎来到 #80DaysOfChallenges 之旅的第 60 天！本次中等难度挑战使用双指针技巧一次遍历并以 O(1) 额外空间删除目标节点，解决了标志性的 删除链表倒数第 N 个节点（LeetCode #19）问题。方案包括 Node 类、用于构建和打印链表的辅助函数，以及用于交互式测试的 main 程序。

示例
链表 1 → 2 → 3 → 4 → 5，n = 2 → 1 → 2 → 3 → 5（删除 4，即倒数第二个节点）

关键要点

Node 类与构造器：轻松构建链表

class Node:
    """Simple singly linked list node."""
    def __init__(self, value: int):
        self.value = value
        self.next = None

def build_linked_list(values: list[int]) -> Node:
    """Build a linked list from a list of integers."""
    if not values:
        return None

    head = Node(values[0])
    curr = head
    for v in values[1:]:
        curr.next = Node(v)
        curr = curr.next
    return head

O(n) 的构建时间；能够优雅地处理空输入列表。

删除函数：哑节点 + 双指针舞蹈

def remove_nth_from_end(head: Node, n: int) -> Node:
    """
    Remove the Nth node from the end using fast/slow pointers.
    Returns the new head after deletion.
    """
    dummy = Node(0)          # Simplifies edge cases (e.g., deleting the head)
    dummy.next = head
    fast = dummy
    slow = dummy

    # Move fast pointer n+1 steps ahead
    for _ in range(n + 1):
        if fast is None:
            return head      # n is larger than the list length
        fast = fast.next

    # Advance both pointers until fast reaches the end
    while fast is not None:
        fast = fast.next
        slow = slow.next

    # Delete the target node
    slow.next = slow.next.next
    return dummy.next

哑节点消除了对头节点删除的特殊情况处理。将 fast 前进 n+1 步后，slow 正好停在待删除节点的前一个位置，从而实现一次遍历的 O(n) 解法。

打印函数与主程序：可视化与输入

def print_linked_list(head: Node) -> None:
    """Print linked list values cleanly."""
    curr = head
    nodes = []
    while curr is not None:
        nodes.append(str(curr.value))
        curr = curr.next
    print(f"Linked List: {' -> '.join(nodes)}")

# Interactive demo
raw_nums = input("Enter list values (space-separated): ").strip()
raw_n = input("Enter n (which node from the end to remove): ").strip()

if not raw_nums or not raw_n:
    print("Invalid input. Exiting.")
    exit()

nums = list(map(int, raw_nums.split()))
n = int(raw_n)

head = build_linked_list(nums)
print("Original list:")
print_linked_list(head)

new_head = remove_nth_from_end(head, n)
print(f"List after removing {n}th node from the end:")
print_linked_list(new_head)

脚本解析空格分隔的整数，构建链表，展示原始结构，执行删除操作，并打印结果链表。

总结与思考

此题展示了双指针技巧在单链表中无需先计算长度即可从末尾访问元素的优雅性。

• 哑节点的作用 – 消除对头节点删除的边界检查。
• 指针间距 – 将 fast 保持在 n+1 个节点前，使 slow 正好位于目标节点之前。
• 一次遍历的高效 – 时间复杂度 O(n)，额外空间 O(1)。

递归方案也是可行的，但对深度较大的链表而言，迭代实现更安全。

后续步骤与资源

• 第 60 题的源码 – scripts/remove_nth_from_end.py
• 主仓库 – 80-days-of-challenges
• 每日更新 – Twitter/X (@Shahrouzlogs)