删除链表末尾的第 N 个

在数据结构中，链表是一个非常重要的基础概念，它由一系列节点组成，每个节点包含数据和指向下一个节点的指针。删除链表末尾的第 N 个节点的操作常见于许多编程题和实际应用中，理解这个操作将有助于我们更好地掌握链表的使用与操作。

链表概况

链表是一种动态数据结构，具有以下优点：插入和删除操作的时间复杂度为 O(1)，而在数组中进行同样的操作则需要 O(n) 的时间。在链表中，节点之间通过指针相连接，由此形成一个链表结构。

链表的定义

一个简单的链表节点定义如下：

type ListNode struct {
    Val  int
    Next *ListNode
}

在这个结构中，Val 是节点存储的数据，Next 则是指向下一个节点的指针。如果 Next 为 nil，说明当前节点是链表的尾部。

问题描述

给定一个链表，要求删除链表末尾的第 N 个节点。这个问题的关键在于如何有效地定位到要删除的节点，并进行适当的调整指针。

技巧与方法

可以通过两种常见的方法来完成这一任务：计算长度法和双指针法。

计算长度法

首先，我们可以遍历一遍链表，计算出链表的长度。然后根据长度和 N 的关系确定要删除的节点的位置，再次遍历链表找到该节点并进行删除：

func removeNthFromEnd(head *ListNode, n int) *ListNode {
    // 计算链表的长度
    length := 0
    current := head
    for current != nil {
        length++
        current = current.Next
    }
    // 如果要删除的是头节点
    if n == length {
        return head.Next
    }
    // 找到要删除的前一个节点
    current = head
    for i := 1; i < length-n; i++ {
        current = current.Next
    }
    // 删除节点
    current.Next = current.Next.Next
    return head
}

双指针法

双指针法更为高效，只需遍历一次链表即可完成操作。通过设置两个指针，初始时让一个指针领先另一个 n 步。随后，两个指针同时移动，直至领先的指针到达链表末尾。此时，后面的指针就正好指向要删除的节点。

func removeNthFromEnd(head *ListNode, n int) *ListNode {
    dummy := &ListNode{Next: head}
    fast, slow := dummy, dummy
    // 让 fast 指针先走 n+1 步
    for i := 0; i < n+1; i++ {
        fast = fast.Next
    }
    // 然后同时移动 fast 和 slow
    for fast != nil {
        fast = fast.Next
        slow = slow.Next
    }
    // 删除目标节点
    slow.Next = slow.Next.Next
    return dummy.Next
}

复杂度分析

对于以上两种方法，时间复杂度都是 O(L)，其中 L 为链表长度，而空间复杂度为 O(1)，因为我们只使用了常数级别的额外空间。双指针法在效率上更具有优势，因为它只需遍历一次链表。

总结

删除链表末尾的第 N 个节点是链表操作中的一个经典问题。无论是选择计算长度法还是双指针法，理解各自的实现原理和适用场景都有助于我们在未来的面试和实际开发中灵活运用。链表作为一种基础数据结构，在数据存储与处理方面有着广泛的应用场景，掌握它的操作可以提升我们的编程能力。