Skip to main content

删除链表的倒数第 N 个结点

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

示例 1： image

输入：head = [1,2,3,4,5], n = 2 输出：[1,2,3,5] 示例 2：

输入：head = [1], n = 1 输出：[] 示例 3：

输入：head = [1,2], n = 1 输出：[1]

双指针法：

方法思路​

  1. 双指针初始化：设置两个指针 first 和 second，均指向虚拟头节点（避免处理头节点被删除的情况）。
  2. 移动第一个指针：将 first 指针向前移动 n+1 步，使 first 和 second 之间间隔 n 个节点。
  3. 同步移动双指针：同时移动 first 和 second，直到 first 指向链表末尾（null）。此时 second 恰好指向倒数第 n+1 个节点（待删除节点的前一个节点）。
  4. 删除目标节点：修改 second 的 next 指针，跳过倒数第 n 个节点。

代码实现​

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
function removeNthFromEnd(head, n) {
    const dummy = new ListNode(0); // 虚拟头节点
    dummy.next = head;
    
    let first = dummy;
    let second = dummy;
    
    // 移动first指针n+1步
    for (let i = 0; i <= n; i++) {
        first = first.next;
    }
    
    // 同步移动双指针
    while (first !== null) {
        first = first.next;
        second = second.next;
    }
    
    // 删除倒数第n个节点
    second.next = second.next.next;
    
    return dummy.next; // 返回真正的头节点
}

复杂度分析​

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

示例验证​

输入：链表 1 → 2 → 3 → 4 → 5，n = 2
输出：1 → 2 → 3 → 5

过程：

  1. 初始化双指针：first 和 second 均指向虚拟头节点 dummy。
  2. 移动 first 指针：first 向前移动 3 步（n+1=3），指向节点 3。
  3. 同步移动双指针：
    • first 移动到节点 4，second 移动到节点 1。
    • first 移动到节点 5，second 移动到节点 2。
    • first 移动到 null，second 指向节点 3（待删除节点 4 的前一个节点）。
  4. 删除节点：将节点 3 的 next 指向节点 5，跳过节点 4。

关键细节说明​

  1. 虚拟头节点的作用：当要删除的是头节点时，虚拟头节点确保 second 能正确指向待删除节点的前一个节点（即虚拟头节点本身）。
  2. 指针间隔：通过 first 先行 n+1 步，确保 second 最终停在倒数第 n+1 个节点，而非倒数第 n 个。
  3. 边界处理：当链表长度为 n 时，first 移动 n+1 步后会指向 null，此时 second 指向虚拟头节点，直接删除头节点即可。

该方法通过双指针巧妙地一次遍历完成删除操作，避免了先计算链表长度的额外开销，是处理链表删除问题的高效解法。