python 删除链表的倒数第 N 个结点 多种解法

解法一：双指针法 这种解法使用两个指针，一个快指针和一个慢指针，它们之间的距离为 N。首先，让快指针先移动 N 步。然后，同时移动快指针和慢指针，直到快指针到达链表末尾。此时，慢指针指向的节点就是要删除的节点的前一个节点。最后，将慢指针的下一个节点指向下下个节点，完成删除操作。

def removeNthFromEnd(head, n):
    dummy = ListNode(0)  # 创建一个虚拟头节点
    dummy.next = head
    fast = dummy
    slow = dummy

    # 快指针先移动 n 步
    for _ in range(n):
        fast = fast.next

    # 同时移动快指针和慢指针
    while fast.next:
        fast = fast.next
        slow = slow.next

    # 删除节点
    slow.next = slow.next.next

    return dummy.next

解法二：计算链表长度法 这种解法需要先遍历链表，计算链表的长度。然后，找到要删除的节点的正向位置，再进行删除操作。

def removeNthFromEnd(head, n):
    length = 0
    dummy = ListNode(0)  # 创建一个虚拟头节点
    dummy.next = head
    current = head

    # 计算链表长度
    while current:
        length += 1
        current = current.next

    length -= n
    current = dummy

    # 找到要删除节点的正向位置
    while length > 0:
        length -= 1
        current = current.next

    # 删除节点
    current.next = current.next.next

    return dummy.next