算法学习笔记

链表——在任意位置插入一个节点

• 图示

• 代码实现

#include<iostream>
using namespace std;
struct Node {//一个节点需要保存一个数据(data)和下一个节点的地址(next)
    int data;
    Node* next;
};
Node* head = NULL;//头节点需要设置为全局变量
void Insert() {//n表示插入的位置
    int data, n;
    cout << "插入的位置为：";
    cin >> n;
    cout << "插入的数据为：";
    cin >> data;
    Node* temp1 = new Node();
    temp1->data = data;
    temp1->next = NULL;
    if (n == 1) {//插入第一位的时候需要特判，此时头节点需要更新
        temp1->next = head;
        head = temp1;
        return;
    }
    Node* temp2 = head;
    for (int i = 0; i < n - 2; i++) {//得到第n-1位节点的地址
        temp2 = temp2->next;
    }
    temp1->next = temp2->next;
    temp2->next = temp1;
}
void Print() {
    Node*temp=head;
    cout << "List is ";
    while (temp != NULL) {
        cout << temp->data;
        temp = temp->next;
    }
    cout << endl;
}
int main() {
    Node*head = NULL;
    Insert();
    Print();
    Insert();
    Print();
    Insert();
    Print();
    Insert();
    Print();
    return 0;
}

• 输出结果