删除链表中的每个第K个节点

删除链表中的每个第K个节点

什么是链表

链表（Linked List）是一种常见的数据结构，它通过指针将一系列的节点串联起来。相比于数组，链表的大小可以动态的改变，可以更高效地进行插入、删除等操作。链表通常包含一个头节点，指向第一个节点，以及一个尾节点，指向最后一个节点。每一个节点包含两个部分，数据域和指针域。数据域保存具体的数据，指针域指向下一个节点。

下面是一个简单的链表示例，每个节点包含一个整数和一个指针：

struct Node {
    int val;        // 数据域，保存一个整数
    Node *next;     // 指针域，指向下一个节点
};
Node *head, *tail;  // 头节点和尾节点

删除链表中的每个第K个节点

对于题目中的问题，我们可以使用快慢指针来解决。具体的做法是，每隔K个节点，就将慢指针指向的节点删除，直到遍历完整个链表。需要注意的是，我们要使用一个临时指针来保存前一个节点，方便删除操作。

下面是实现代码示例：

Node *deleteKNodes(Node *head, int k) {
    if (k <= 0) return head;    // 特判K<=0的情况
    if (k == 1) return nullptr; // 如果K等于1，直接返回空链表
    Node *dummy = new Node(-1, head);  // 创建一个虚拟节点
    Node *pre = dummy, *cur = head;    // pre指向前一个节点，cur指向当前节点
    int cnt = 0;                       // 计数器，用于记录当前遍历的位置
    while (cur) {
        cnt++;           // 自增计数器
        if (cnt % k == 0) {  // 如果已经到了第K个节点
            pre->next = cur->next;  // 将前一个节点的指针指向当前节点的下一个节点
            cur = cur->next;        // 将当前节点指向下一个节点
        } else {
            pre = cur;     // 将前一个节点指向当前节点
            cur = cur->next;  // 将当前节点指向下一个节点
        }
    }
    return dummy->next;  // 返回已删除的链表
}

时间复杂度分析

上面的代码中，我们只遍历了一次链表，时间复杂度是O(N)。因此，删除链表中每个第K个节点的算法的复杂度应该是O(N)。

空间复杂度分析

空间复杂度是O(1)，因为我们只使用了常数级别的变量。

参考资料

数据结构 01 链表 - 极客时间

链表 - 维基百科