List怎么删除链表的倒数第N个节点

在编程中，链表是一种常见的数据结构，它由一系列节点组成，每个节点包含数据和指向下一个节点的指针。链表的操作包括插入、删除、查找等。本文将重点讨论如何删除链表的倒数第N个节点。

问题描述

给定一个链表，删除链表的倒数第N个节点，并返回链表的头节点。例如，给定链表 1->2->3->4->5 和 N = 2，删除倒数第2个节点后，链表变为 1->2->3->5。

解决思路

要删除链表的倒数第N个节点，我们需要找到该节点的前一个节点，然后将其指针指向下一个节点。由于链表是单向的，我们无法直接从后向前遍历，因此需要采用一些技巧。

双指针法

双指针法是解决此类问题的常用方法。具体步骤如下：

1. 初始化两个指针：fast 和 slow，都指向链表的头节点。
2. 移动 fast 指针：将 fast 指针向前移动 N 步，使得 fast 和 slow 之间相隔 N 个节点。
3. 同时移动 fast 和 slow 指针：当 fast 指针到达链表末尾时，slow 指针正好指向倒数第 N 个节点的前一个节点。
4. 删除节点：将 slow 指针的 next 指向 slow->next->next，从而删除倒数第 N 个节点。

代码实现

以下是使用双指针法删除链表倒数第N个节点的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)
    dummy.next = head
    fast = slow = dummy
    
    # 移动 fast 指针，使其与 slow 指针相隔 n 个节点
    for _ in range(n):
        fast = fast.next
    
    # 同时移动 fast 和 slow 指针，直到 fast 到达链表末尾
    while fast.next:
        fast = fast.next
        slow = slow.next
    
    # 删除倒数第 n 个节点
    slow.next = slow.next.next
    
    return dummy.next

示例

假设链表为 1->2->3->4->5，N = 2，则执行上述代码后，链表变为 1->2->3->5。

复杂度分析

• 时间复杂度：O(L)，其中 L 是链表的长度。我们只需要遍历链表一次。
• 空间复杂度：O(1)，我们只使用了常数级别的额外空间。

总结

通过双指针法，我们可以高效地删除链表的倒数第N个节点。这种方法不仅简单易懂，而且时间复杂度较低，适用于大多数链表操作场景。希望本文对你理解链表的操作有所帮助。