数据结构：循环链表中插入节点（Inserting in a Circular Linked List）

目录

插入位置的分类

第一种情况：插入到空链表

  第二种情况：插入到头部（成为新的 head）

 第三种情况：插入到尾部（尾插）

  第四种情况：插入到中间某个位置

  统一第一性模型（所有插入逻辑的共性）

插入操作的本质是什么？

我们从根本出发：

插入 = 新建一个节点，把它放在链表中的某个位置，并且保证链表结构仍然成立

对于循环链表来说，链表结构的成立条件是：

• 每个节点 next 指向下一个节点

• 最后一个节点的 next 指向头节点 head

所以插入操作必须满足两个要求：

1. 新节点正确链接在指定位置

2. 链表保持“环”的结构不变

插入位置的分类

我们先明确，插入有多种位置选择，不同位置的插入逻辑完全不同。

我们要写一个函数：

void insert(Node** headRef, int value, int pos);

• headRef：指向链表头指针的指针

• value：要插入的整数值

• pos：插入的位置（从 0 开始）

  • pos == 0：插入到头部

  • pos > 0：插入到第 pos 个位置后（尾部就是最后一个位置后）

我们现在按照这四种情况一步步推导插入的逻辑。

第一种情况：插入到空链表

这是最基础的情况：

• 链表为空，即 head == NULL

• 新建一个节点，next 应该指向自己，形成闭环

第一性推导：

Node* newNode = createNode(x);
newNode->next = newNode;
head = newNode;

 结构图：

[x]
 ^ \
 |__/

代码实现

Node* createNode(int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = value;
    newNode->next = NULL;
    return newNode;
}

void insertToEmpty(Node** headRef, int value) {
    Node* newNode = createNode(value);
    newNode->next = newNode;  // 自己指向自己
    *headRef = newNode;       // 设置 head
}

    // 情况1：空链表
    if (*headRef == NULL) {
        newNode->next = newNode;
        *headRef = newNode;
        return;
    }

  第二种情况：插入到头部（成为新的 head）

目标：把新节点插在链表最前面，即 newNode -> oldHead -> ... -> lastNode -> newNode

难点在于：

• 找到尾节点（因为它要指向新的头）

• 然后把 newNode->next = head

• 再把 尾节点的 next 改成 newNode

• 最后 head = newNode

步骤按第一性拆解如下：

1. 创建新节点 newNode

2. 设置 newNode->next = head

3. 遍历找到尾节点：即 tail->next == head

4. 设置 tail->next = newNode

5. 更新 head = newNode

void insertAtHead(Node** headRef, int value) {
    Node* newNode = createNode(value);

    if (*headRef == NULL) {
        // 空链表特判
        newNode->next = newNode;
        *headRef = newNode;
        return;
    }

    Node* tail = *headRef;
    while (tail->next != *headRef) {
        tail = tail->next;
    }

    newNode->next = *headRef;
    tail->next = newNode;
    *headRef = newNode; // 更新头指针
}

    // 情况2：插入到头部
    if (pos == 0) {
        Node* tail = *headRef;
        while (tail->next != *headRef) {
            tail = tail->next;
        }

        newNode->next = *headRef;
        tail->next = newNode;
        *headRef = newNode;
        return;
    }

 第三种情况：插入到尾部（尾插）

尾插和头插很像，只是不用换 head。

第一性推导如下：

1. 创建新节点 newNode

2. 遍历找到尾节点（tail->next == head）

3. 设置：

   • tail->next = newNode

   • newNode->next = head

结构图变化：

A -> B -> C -> A
插入后：A -> B -> C -> X -> A

注意：

• head 不变

• 环形结构完整保留

void insertAtTail(Node** headRef, int value) {
    Node* newNode = createNode(value);

    if (*headRef == NULL) {
        newNode->next = newNode;
        *headRef = newNode;
        return;
    }

    Node* tail = *headRef;
    while (tail->next != *headRef) {
        tail = tail->next;
    }

    tail->next = newNode;
    newNode->next = *headRef;
}

  第四种情况：插入到中间某个位置

比如“在第 k 个节点后插入”

第一性推导：

1. 创建新节点 newNode

2. 从 head 开始遍历 k 次，定位到第 k 个节点 temp

3. 设置：

   • newNode->next = temp->next

   • temp->next = newNode

结构图变化：

插入前：A -> B -> C -> D -> A
插入后：A -> B -> X -> C -> D -> A

• 只需操作前一个节点 temp

• 环结构自动延续，因为你没有动尾指针的指向逻辑（除非你插在最后）

void insertAfterKth(Node* head, int k, int value) {
    if (head == NULL) return;

    Node* newNode = createNode(value);
    Node* current = head;

    // 移动 k-1 次找到第 k 个节点
    for (int i = 1; i < k; ++i) {
        current = current->next;
        if (current == head) return; // k 超出长度
    }

    newNode->next = current->next;
    current->next = newNode;
}

    // 情况3和4：插入到中间或尾部
    Node* temp = *headRef;

    // 向后走 pos-1 次，找到插入点的前一个节点
    for (int i = 1; i < pos; ++i) {
        temp = temp->next;

        // 如果已经一圈回到头，说明 pos 超出长度，直接尾插
        if (temp == *headRef) break;
    }

    newNode->next = temp->next;
    temp->next = newNode;

  统一第一性模型（所有插入逻辑的共性）

 所有插入操作都满足以下公式：

newNode->next = 插入点后一个节点;
插入点->next = newNode;

唯一区别是：

• 插入点的位置不同

• 是否需要更新 head

• 是否需要更新尾节点的指向

完整代码

void insert(Node** headRef, int value, int pos) {
    Node* newNode = createNode(value);

    // 情况1：空链表
    if (*headRef == NULL) {
        newNode->next = newNode;
        *headRef = newNode;
        return;
    }

    // 情况2：插入到头部
    if (pos == 0) {
        Node* tail = *headRef;
        while (tail->next != *headRef) {
            tail = tail->next;
        }

        newNode->next = *headRef;
        tail->next = newNode;
        *headRef = newNode;
        return;
    }

    // 情况3和4：插入到中间或尾部
    Node* temp = *headRef;

    // 向后走 pos-1 次，找到插入点的前一个节点
    for (int i = 1; i < pos; ++i) {
        temp = temp->next;

        // 如果已经一圈回到头，说明 pos 超出长度，直接尾插
        if (temp == *headRef) break;
    }

    newNode->next = temp->next;
    temp->next = newNode;
}

删除操作略