力扣面试经典——19题

💡 参考代码：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

/**
 * 删除链表的倒数第n个节点
 * @param head 链表头节点
 * @param n 倒数第n个节点
 * @return 返回删除节点后的链表头节点
 */
struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
    // 创建虚拟头节点，简化边界情况处理
    struct ListNode* dummy = (struct ListNode*)malloc(sizeof(struct ListNode));
    dummy->next = head;
    
    // 定义快慢指针
    struct ListNode* fast = dummy;
    struct ListNode* slow = dummy;
    
    // 快指针先向前移动n+1步
    // 这样当fast到达末尾时，slow正好指向要删除节点的前一个节点
    for (int i = 0; i <= n; i++) {
        fast = fast->next;
    }
    
    // 同时移动快慢指针，直到快指针到达链表末尾
    while (fast != NULL) {
        fast = fast->next;
        slow = slow->next;
    }
    
    // 删除倒数第n个节点
    struct ListNode* temp = slow->next;
    slow->next = slow->next->next;
    free(temp);
    
    // 保存结果并释放虚拟节点
    struct ListNode* result = dummy->next;
    free(dummy);
    
    return result;
}

📖 总结：

点击展开题目总结

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

---

1️⃣ 题目核心信息

🎯 功能描述：删除链表中的倒数第 n 个节点并返回修改后的链表头节点

📥 输入输出：

• 输入：
  • head: 链表的头节点，表示链表的起始位置
  • n: 正整数，表示要删除倒数第几个节点
• 输出：返回删除指定节点后的链表头节点

---

2️⃣ 实现原理

💡 核心思路：使用双指针技术，在一次遍历中定位到待删除节点的前驱节点

📋 实现步骤：

1. 创建虚拟头节点，简化边界处理
2. 设置快慢两个指针，初始都指向虚拟头节点
3. 快指针先向前移动 n+1 步
4. 快慢指针同时移动直到快指针到达链表末尾
5. 此时慢指针正好指向待删除节点的前一个节点
6. 执行删除操作并释放内存
7. 返回处理后的链表头节点

---

3️⃣ 关键点解析

🎯 代码技巧

• 使用虚拟头节点简化头节点删除的边界情况处理
• 双指针技术实现一次遍历完成删除操作
• 快指针先走 n+1 步，确保慢指针能准确定位到待删除节点的前驱节点

4️⃣ 使用场景

✅ 适用情况：

• 需要删除链表中倒数第 n 个节点的操作
• 对链表进行一次遍历就能完成的删除操作
• 需要简化链表头节点删除边界处理的场景

⚠️ 前提条件：

• 链表至少有 n 个节点
• n 是有效的正整数（1 <= n <= 链表长度）

5️⃣ 复杂度分析

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

6️⃣ 注意事项

🚩 边界情况：

• 删除头节点的情况（n 等于链表长度）
• 链表只有一个节点的情况
• 删除尾节点的情况（n 等于 1）

💥 易错点：

• 忘记释放被删除节点的内存导致内存泄漏
• 没有正确处理删除头节点的特殊情况
• 快指针移动步数计算错误导致定位不准确

7️⃣ 补充说明

以示例1为例：链表为 [1,2,3,4,5]，n = 2，需要删除倒数第2个节点（即值为4的节点）。

初始状态：

dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> NULL
  ↑
fast, slow

第1步：创建虚拟头节点，并让快慢指针都指向它

dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> NULL
  ↑
fast, slow

第2步：快指针先向前移动 n+1 = 3 步

dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> NULL
  ↑      ↑         ↑
slow   fast      fast
              (第3步)

移动过程：

• 第1次移动后：fast 指向节点 1
• 第2次移动后：fast 指向节点 2
• 第3次移动后：fast 指向节点 3

此时状态：

dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> NULL
  ↑              ↑
slow           fast

第3步：快慢指针同时向前移动，直到 fast 到达 NULL 第1次同时移动后：

dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> NULL
         ↑         ↑              ↑
       slow      fast           fast

第2次同时移动后：

dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> NULL
              ↑         ↑         ↑
            slow      fast      (NULL)

此时 fast 已经到达 NULL，移动结束。

第4步：执行删除操作

此时 slow 指向节点 2，slow->next 指向节点 4（待删除节点）。 执行 slow->next = slow->next->next 操作：

dummy -> 1 -> 2 -> 3 -----> 5 -> NULL
              ↓             ↑
              └-------------┘

第5步：释放被删除节点的内存并返回结果

• 释放节点 4 的内存
• 返回 dummy->next，即节点 1，最终结果为 [1,2,3,5]

通过这种方式，我们只需要一次遍历就能找到并删除倒数第 n 个节点，时间复杂度为 O(sz)，空间复杂度为 O(1)。

加载评论中...