迹忆客 专注技术分享

在本文中，我们将学习如何在链表中插入节点。我们可以看到出现了 4 种不同的情况。

1. 我们要在链接列表的开头之前插入一个节点。此操作类似于堆栈中的推入操作。
2. 我们要在链接列表的末尾（即尾节点旁边）插入一个节点。
3. 我们想在链接列表的第 i 个位置插入一个节点。
4. 我们有该节点的引用，之后我们要插入新节点。

链表插入算法

令 head 为指向链表第一个节点的指针，令 x 为要插入链表中的数据。

在链接列表 push() 的开头插入节点

• 用数据 x 创建一个新节点 temp。
• 将 temp->next 设置为 head，以在 head 之前插入 temp。
• 将 temp 设置为链接列表的开头。

在链接列表 append() 的末尾插入节点

• 用数据 x 创建一个新节点 temp。
• 初始化指向 head 的 tail。
• 如果链接列表为空，则将 temp 设置为链接列表的 head，然后返回。
• 否则，迭代链接列表的末尾，使 tail->next！=NULL，以便你到达最后一个元素
• 将 tail->next 设置为 temp。

在链接列表 insertNpos() 的 i-th 位置处插入节点

• 如果位置 pos<=0，则返回；否则返回 0。
• 如果 pos==0 并且 head 为空，则创建一个数据为 x 的新节点并将其设置为 head。
• 如果 pos==1，则调用 push()。
• 另外，用数据 x 创建一个新节点 temp。
• 初始化指向 head 的 curr。
• 当 pos-- 时，执行以下操作。

  • 如果 pos==1，

    • 如果 curr 不是 NULL
      • 将 temp->next 设置为 curr->next，以便在 curr 之后插入 temp。
      • 将 curr->next 设置为 temp，以将 curr 连接到 temp。
    • 返回;

  • 否则将 curr 设置为 curr->next。

在给定节点的引用旁边插入节点 - insertAfter()

• 如果 prev==NULL，则返回；
• 用数据 x 创建一个新节点 curr。
• 将 curr->next 指向 prev->next 以在 prev 之后添加新节点。
• 将 prev->next 指向 curr 以完成插入。

链表插入图

假设我们有一个节点 temp，其数据值等于 5，我们想将其插入链表中。让我们考虑所有 4 种情况，并说明上述算法是如何工作的。

在链接列表的开头插入节点 - push()

• 将 temp 的指针设置为 head。
• 将 head 指向 temp。

在链接列表 append() 的末尾插入节点

• 将 curr 指向 head，数据为 2。
• 将 curr 设置为 curr->next，并将其移动到数据为 3 的节点。
• 将 curr 设置为 curr->next，并将其移动到数据为 4 的节点。
• 退出 while 循环并将 curr->next 设置为 temp

在链接列表的 i-th 位置处插入节点 - insertNpos()

我们将节点插入到位置 3。

• 将 curr 指向 head，数据为 1，pos=pos-1=2。
• 将 curr 设置为 curr->next，并将其移动到数据为 3，pos=pos -1=1 的节点。
• 将 temp->next 设置为 curr->next，以便在 curr 之后插入 temp。
• 将 curr->next 设置为 temp，以在 curr 和 curr->next 之间完成 temp 的插入。

在给定节点 insertAfter() 的引用旁边插入节点

• 将 temp->next 设置为 prev->next，以在 prev 和 prev->next 之间插入 temp。
• 将 prev->next 设置为 temp 以完成插入。

链表插入实现

#include <bits/stdc++.h>
using namespace std;

class Node {
    public:
        int data;
        Node* next;
        Node(int x) {
            this->data = x;
            this->next = NULL;
        }
};

void push(Node** head, int x)
{
    Node* temp = new Node(x);
    temp->next = (*head);
    (*head) = temp;
}

void insertAfter(Node* prev, int x)
{
    if (prev == NULL) {
        return;
    }
    Node* curr = new Node(x);
    curr->next = prev->next;
    prev->next = curr;
}

void printList(Node* head)
{
    Node*curr = head;
    while (curr != NULL) {
        cout << curr->data << " ";
        curr = curr->next;
    }
}
void insertNpos(Node**head, int x, int pos) {
    if (pos <= 0) {
        return;
    }
    if (!head && pos == 1) {
        *head = new Node(x);
    }
    else if (pos == 1) {
        push(head, x);
    }
    Node* temp = new Node(x);
    Node*curr = *head;
    while (pos--) {
        if (pos == 1) {
            if (curr) {
                temp->next = curr->next;
                curr->next = temp;
            }
            return;
        }
        curr = curr->next;
    }
}
void append(Node** head, int x)
{
    Node* temp = new Node(x);
    Node *tail = *head;
    if (*head == NULL)
    {
        *head = temp;
        return;
    }
    while (tail->next != NULL)
        tail = tail->next;
    tail->next = temp;
    return;
}

int main()
{
    Node* head = new Node(1);
    head -> next = new Node(2);
    printList(head); cout << "\n";
    push(&head, 3);
    push(&head, 4);
    printList(head); cout << "\n";
    append(&head, 5);
    printList(head); cout << "\n";
    insertAfter(head->next->next, 6);
    printList(head); cout << "\n";
    insertNpos(&head, 24, 2);
    printList(head);
    return 0;
}

链表插入算法的复杂度

时间复杂度

• 平均情况

要将节点插入链表中的第 i 个位置，我们必须访问 i 个节点。因此，时间复杂度约为 O(i)。而且我们在链表中有 n 个节点，因此平均情况下的时间复杂度为 O(n/2) 或 O(n)。时间复杂度约为 O(n)。

• 最佳情况

最好的情况是，当我们想在链表的开头插入一个节点，或者在插入站点之前有对该节点的引用时。最佳情况下的时间复杂度是 O(1)。

• 最坏情况

最差的时间复杂度是 O(n)。这与平均情况下的时间复杂度相同。

空间复杂度

该插入算法的空间复杂度为 O(1)，因为除 curr 指针外不需要其他空间。