链表（Linked List）

         链表是一种线性数据结构，由一系列节点（Node）通过指针链接在一起。与数组不同，链表中的元素在内存中不需要连续存储，每个节点包含两部分：

• 数据部分：存储节点的值或数据。
• 指针部分：存储指向下一个节点的地址（单链表）或上一个和下一个节点的地址（双向链表）。

         链表的类型主要有以下几种：

• 单链表：每个节点只指向下一个节点。
• 双向链表：每个节点既有指向下一个节点的指针，也有指向上一个节点的指针。
• 循环链表：链表的最后一个节点指向链表的头节点，形成循环。

         链表的特点：

• 动态大小：可以根据需要动态地增加或减少元素，无需预分配存储空间。
• 插入/删除效率高：在链表的任意位置进行插入或删除操作只需修改指针，不涉及大量元素的移动，效率较高。
• 随机访问效率低：由于链表不支持直接访问任意位置的元素，需要通过遍历来查找特定位置的节点。

         如下图所示：

题目要求

题目描述：给定一个单链表和一个整数 n，请删除链表的倒数第 n 个节点，并返回链表的头节点。

输入输出示例：

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

要求：尝试在一次遍历内解决问题，并保证时间复杂度为 O(N)。

---

解题思路

快慢指针法：

• 设置两个指针 fast 和 slow。
• 先让 fast 指针移动 n 步，这样 fast 和 slow之间就相隔 n 个节点。
• 接下来，两个指针同时移动，当 fast 到达链表末尾时，slow正好停在要删除节点的前一个位置。
• 通过调整 slow 的指针指向，完成节点删除。

特殊情况处理：

• 如果链表只有一个节点，直接返回 NULL。
• 如果要删除的节点是头节点，特殊处理即可。

算法过程

1. 创建一个哑节点（dummy node）指向链表头部，用于简化操作。
2. 初始化两个指针 fast  和 slow，均指向哑节点。
3. 移动 fast  指针 n+1 步，保持 slow和 fast  之间的距离为 n+1。
4. 同时移动 fast 和 slow，直到 fast 到达链表末尾。
5. 调整 slow->next 指向，跳过目标节点，完成删除操作。
6. 返回哑节点的下一节点 dummy->next 作为新的头节点。

---

示例代码

C 实现

#include <stdio.h>  // 标准输入输出库
#include <stdlib.h> // 动态内存分配和释放的库

// 定义链表节点结构
typedef struct ListNode {
    int val;              // 节点的值
    struct ListNode *next; // 指向下一个节点的指针
} ListNode;

// 辅助函数：创建新节点
ListNode* createNode(int val) {
    ListNode* newNode = (ListNode*)malloc(sizeof(ListNode)); // 分配内存给新节点
    newNode->val = val;  // 设置节点值
    newNode->next = NULL; // 初始化为没有下一个节点
    return newNode;      // 返回新创建的节点
}

// 删除链表的倒数第n个节点
ListNode* removeNthFromEnd(ListNode* head, int n) {
    // 创建一个哑节点（dummy），方便操作链表头部
    ListNode* dummy = createNode(0);
    dummy->next = head;  // 哑节点的next指向链表头部
    ListNode *fast = dummy, *slow = dummy; // 初始化快慢指针都指向哑节点

    // 让fast指针先移动n+1步，使得fast和slow之间间隔n个节点
    for (int i = 0; i <= n; i++) {
        fast = fast->next; // fast每次向前移动一步
    }

    // 快慢指针同时移动，直到fast到达链表末尾
    while (fast != NULL) {
        fast = fast->next; // fast向前移动一步
        slow = slow->next; // slow向前移动一步
    }

    // 此时，slow指向要删除节点的前一个节点
    ListNode* temp = slow->next; // 保存要删除的节点
    slow->next = slow->next->next; // 跳过目标节点，完成删除
    free(temp); // 释放目标节点的内存

    // 返回链表的新头节点
    ListNode* newHead = dummy->next; // 哑节点的next即为新头节点
    free(dummy); // 释放哑节点的内存
    return newHead; // 返回新链表的头节点
}

// 辅助函数：打印链表
void printList(ListNode* head) {
    while (head != NULL) {         // 遍历链表直到尾节点
        printf("%d -> ", head->val); // 打印当前节点的值
        head = head->next;         // 移动到下一个节点
    }
    printf("NULL\n"); // 打印链表末尾标记
}

// 主函数
int main() 
{
    // 创建链表 1 -> 2 -> 3 -> 4 -> 5
    ListNode* head = createNode(1);
    head->next = createNode(2);
    head->next->next = createNode(3);
    head->next->next->next = createNode(4);
    head->next->next->next->next = createNode(5);

    // 打印原链表
    printf("Original linked list: ");
    printList(head);

    int n = 2; // 要删除倒数第n个节点
    head = removeNthFromEnd(head, n); // 调用函数删除目标节点

    // 打印删除后的链表
    printf("after deleting the last% d node: ", n);
    printList(head);

    return 0; // 程序结束
}

C 实现

#include <iostream> // 标准输入输出流库
using namespace std;

// 定义链表节点结构
struct ListNode {
    int val;           // 节点的值
    ListNode* next;    // 指向下一个节点的指针
    ListNode(int x) : val(x), next(nullptr) {} // 构造函数初始化节点
};

// 删除链表的倒数第n个节点
ListNode* removeNthFromEnd(ListNode* head, int n) {
    // 创建一个哑节点（dummy），方便操作链表头部
    ListNode* dummy = new ListNode(0);
    dummy->next = head; // 哑节点的next指向链表头部
    ListNode *fast = dummy, *slow = dummy; // 初始化快慢指针都指向哑节点

    // 让fast指针先移动n+1步，使得fast和slow之间间隔n个节点
    for (int i = 0; i <= n; i++) {
        fast = fast->next; // fast每次向前移动一步
    }

    // 快慢指针同时移动，直到fast到达链表末尾
    while (fast != nullptr) {
        fast = fast->next; // fast向前移动一步
        slow = slow->next; // slow向前移动一步
    }

    // 此时，slow指向要删除节点的前一个节点
    ListNode* temp = slow->next; // 保存要删除的节点
    slow->next = slow->next->next; // 跳过目标节点，完成删除
    delete temp; // 释放目标节点的内存

    // 返回链表的新头节点
    ListNode* newHead = dummy->next; // 哑节点的next即为新头节点
    delete dummy; // 释放哑节点的内存
    return newHead; // 返回新链表的头节点
}

// 辅助函数：打印链表
void printList(ListNode* head) {
    while (head != nullptr) {       // 遍历链表直到尾节点
        cout << head->val << " -> "; // 打印当前节点的值
        head = head->next;          // 移动到下一个节点
    }
    cout << "NULL" << endl; // 打印链表末尾标记
}

// 主函数
int main() 
{
    // 创建链表 1 -> 2 -> 3 -> 4 -> 5
    ListNode* head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);
    head->next->next->next = new ListNode(4);
    head->next->next->next->next = new ListNode(5);

    // 打印原链表
    cout << "Original linked list: ";
    printList(head);

    int n = 2; // 要删除倒数第n个节点
    head = removeNthFromEnd(head, n); // 调用函数删除目标节点

    // 打印删除后的链表
    cout << "after deleting the last " << n << " node: ";
    printList(head);

    return 0; // 程序结束
}